#include<iostream>
#include<fstream>
using namespace std;
const int ii=(1ll<<31)-1;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int N,M,d[50005];
struct muchie
{
    int x,y,c;
}m[50005];
int main()
{
    in>>N>>M;
    int i,a,b,c;
    for(i=1;i<=M;++i)
    {
        in>>a>>b>>c;
        m[i].x=a;
        m[i].y=b;
        m[i].c=c;
    }
    for(i=2;i<=N;++i) d[i]=ii;
    int pas=0;
    while(pas<=N)
    {
        for(i=1;i<=M;++i)
        {
            a=m[i].x;
            b=m[i].y;
            c=m[i].c;
            if(d[b]>d[a]+c) d[b]=d[a]+c;
        }
        ++pas;
    }
    for(i=2;i<=N;++i) out<<d[i]<<' ';
    out<<'\n';
}