#include<iostream>
#include<fstream>
#include<vector>
#define ii 250000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,d[50005];
bool viz[50005];
struct fiu
{
    int v,cost;
};
vector<fiu> v[50005];
vector<fiu>::iterator it;
int main()
{
    in>>n>>m;
    int i,a,b,x;
    fiu f;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>x;
        if(a==1) d[b]=x;
        f.v=b; f.cost=x;
        v[a].push_back(f);
    }
    x=1;
    for(i=1;i<=n;i++) d[i]=(d[i])? d[i] : ii;
    d[1]=0;
    viz[1]=1;
    int ok=1,m,k;

    while(ok)
    {
        m=ii;
        for(i=1;i<=n;i++)
        {
            if(d[i]<m && !viz[i]) m=d[i],k=i;
        }
        //cout<<k<<'\n';
        if(m<ii)
        {
            viz[k]=1;
            for(it=v[k].begin();it!=v[k].end();++it)
            {
                if(d[it->v]> d[k]+ it->cost) d[it->v]=d[k]+ it->cost;
                //cout<<it->v<<' ';
            }
        }
        else ok=0;
    }
    for(i=2;i<=n;i++) if(d[i]<ii) out<<d[i]<<' '; else out<<0<<' ';
    out<<'\n';
}