#include<fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
long n,m,i,j,k,l,ok,d[50001];
struct bbb{
long x,y,c;}g[250001];

int main()
{
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>g[i].x>>g[i].y>>g[i].c;
        if(g[i].x==1) d[g[i].y]=g[i].c;
    }

    for(i=2;i<=n;++i) if(d[i]==0) d[i]=9999999999;

    do{
    ok=0;
    for(i=1;i<=m;++i)
    {
        if(d[g[i].y]>d[g[i].x]+g[i].c)
        {
            d[g[i].y]=d[g[i].x]+g[i].c;
            ok=1;
        }
    }
    }while(ok==1);

    for(i=2;i<=n;++i) if(d[i]==9999999999) out<<0<<" ";
                         else out<<d[i]<<" ";

    return 0;
}