#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
FILE *in,*out;
struct edge
{
    int t,l;
}vertex;
struct lst
{
    vector<edge>v;
}adj[50001];
const int inf=2000000000;
int n,edges,dist[50001],L;
int heap[50001];
vector<edge>::iterator it;
void heap_pop()
{
    heap[1]=heap[L];
    heap[L]=0;
    --L;
    int x=1,y=0,a;
    while(x!=y)
    {
        y=x;
        if(y*2<=L&&dist[heap[x]]>dist[heap[y*2]])x=y*2;
        if(y*2+1<=L&&dist[heap[x]]>dist[heap[y*2+1]])x=y*2+1;
        a=heap[x];
        heap[x]=heap[y];
        heap[y]=a;
    }
}
void heap_push()
{
    int a,ll=L;
    while(ll/2&&dist[heap[ll/2]]>dist[heap[ll]])
    {
        a=heap[ll];
        heap[ll]=heap[ll/2];
        heap[ll/2]=a;
        ll/=2;
    }
}
int main()
{
    in=fopen("dijkstra.in","r");
    out=fopen("dijkstra.out","w");
    int x,i;
    fscanf(in,"%d%d",&n,&edges);
    for(i=1;i<=edges;++i)
    {
        fscanf(in,"%d%d%d",&x,&vertex.t,&vertex.l);
        adj[x].v.push_back(vertex);
    }
    heap[++L]=1;
    for(i=2;i<=n;++i)dist[i]=inf;
    while(L)
    {
        x=heap[1];
        heap_pop();
        for(it=adj[x].v.begin();it!=adj[x].v.end();++it)if(dist[(*it).t]>(*it).l+dist[x])
        {
            dist[(*it).t]=(*it).l+dist[x];
            heap[++L]=(*it).t;heap_push();
        }
    }
    for(i=2;i<=n;++i)
    {
        if(dist[i]==inf)fprintf(out,"0 ");
        else fprintf(out,"%d ",dist[i]);
    }
    fclose(in);fclose(out);
    return 0;
}