#include <cstdio>
int main ()
{
    int n,m,i,a,b,node[5],eg[5][5],ans=0;
    for(int i=0;i<5;i++){
        for(int j=0;j<7;j++){
            node[i]=1000;
            eg[i][j]=1000;
        }
    }
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        scanf("%d",&eg[a][b]);
    }
    node[0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==0&&eg[i][j]!=1000)node[j]=eg[i][j];
            else if(eg[i][j]+node[i]<node[j]){
                node[j]=eg[i][j]+node[i];
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d\n",node[i]);
    }
    return 0;
}