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

int main()
{
    long x,y,c,i;

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

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

    do{
    ok=1;
    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=0;
        }
    }
    }while(!ok);

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

    return 0;
}