#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;
bool mark[50001];
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(2*y==L)
        {
            if(dist[heap[2*y]]<dist[heap[y]])x=2*y;
            a=heap[x];
            heap[x]=heap[y];
            heap[y]=a;
            break;
        }
        else if(2*y+1<=L)
        {
            if(dist[heap[2*y+1]]<=dist[heap[2*y]])x=2*y+1;
            else x=2*y;
        }
        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,checked=0;
    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(checked<n)
    {
        ++checked;
        x=heap[1];
        heap_pop();
        mark[x]=1;
        for(it=adj[x].v.begin();it!=adj[x].v.end();++it)if(!mark[(*it).t]&&dist[(*it).t]>(*it).l+dist[x])
        {
            dist[(*it).t]=(*it).l+dist[x];
            heap[++L]=(*it).t;heap_push();
        }
        /*for(itt=heap.begin();itt!=heap.end();++itt)fprintf(out,"%d ",(*itt));
        fprintf(out,"\n\n");*/
    }
    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;
}