#include<fstream>
#include<queue>
#define inf 32000
using namespace std;
struct nod{int info,c;nod*adr;}*v[50003],*p;
int n,m,x,y,c,i,viz[50002],dist[50002];
queue< pair<int,int> > Q;
void dijkstra_coada(int nd)
{int d;
    Q.push(make_pair(nd,0) );
    viz[nd]=1;
    for(i=1;i<=n;i++)
    dist[i]=inf;
    while(!Q.empty())
    {
        p=v[Q.front().first];
        d=Q.front().second;
        Q.pop();
        while(p)
        {
            if( !viz[p->info] || d + p->c < dist[p->info] )
            {
                dist[p->info] = d + p->c;
                Q.push( make_pair(p->info, dist[p->info]) );
                viz[p->info]=1;
            }
            p=p->adr;
        }
    }
}
int main()
{
    ifstream f("dijkstra.in");ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        p=new nod;
        p->info=y; p->c=c; p->adr=v[x]; v[x]=p;
    }
    dijkstra_coada(1);
    for(i=2;i<=n;i++)
     if(dist[i]==inf)g<<0; else g<<dist[i]<<" ";
    f.close();g.close();
    return 0;
}