#include <iostream>
#include <fstream>
#define pinf 1000000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n , a[105][105],m, viz[105], d[105], t[105];//d - vectorul distanta , t - vectorul de tati

int main()
{
    int i , j , x,y,c , p=1;
    fin >> n >> m;
    for(i =1 ; i <= n ; ++i)
        {for(j = 1 ; j <= m ; ++j)
            if(i==j)
            a[i][j]=0;
            else
            a[i][j] = pinf;
        }
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
     a[x][y] = c;
    }
    for(i =1 ; i <= n ; i ++ )
    {
        d[i] = a[p][i];
        // t[i] = p;
    }
    viz[p] = 1;
    //t[p] = 0;
    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];
            //  t[i] = pmin;
        }
    }
    for(i = 2 ; i <= n ; i++)
    {
        if(d[i]==pinf)
            fout<<"-1 ";
        else
            fout << d[i]<< " ";
    }
    return 0;
}