#include <iostream>
#include<fstream>
#define pinf 1000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int **a,n,m,p,*d,*viz;
int main()
{
    int i , j , x,y,c , p;
    fin >> n >>m;
    p=1;
    a=new int *[n];
    viz=new int [n];
    d=new int [n];
    for(i =1 ; i <= n ; i++)
    {
        d[i]=0;
        viz[i]=0;
        a[i]=new int [n+1];
        for(j = 1 ; j <= n ; j++)
            a[i][j] = pinf;
    }
    for(int j=1; j<=m; j++)
    {
        fin >> x >> y >> c;
        a[x][y] =c;
    }
    for(i =1 ; i <= n ; i ++ )
    {
        d[i] = a[p][i];
    }
    viz[p] = 1;
    d[p] = 0;
    d[0] = pinf;
    for(int k = 1 ; k <=n ; k++)
    {
        int pmin = 0;
        for(i = 1 ; i <= n ; i++)
            if(viz[i] == 0 && d[i] < d[pmin])
                pmin = i;
        if(pmin > -1)
        {
            viz[pmin] = 1;
            for(i = 1; i <= n ; i++)
                if(viz[i]==0&&d[i] > d[pmin] + a[pmin][i])
                    d[i] = d[pmin] + a[pmin][i];
        }
    }
    for(i = 2 ; i <= n ; i++)
    {
        if(d[i]==pinf)
            fout<<"0 ";
        else
            fout << d[i]<<" ";
            delete []d;
            delete [] a[i];
    }
    return 0;
}