#include <bits/stdc++.h>
#define Nmax 50001
#define INF 2e9+1
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct graph
{
    int nod;
    int cost;
    graph *next;
};
int n,m,k;
graph *a[Nmax];
int d[Nmax];
int h[Nmax];
int poz[Nmax];
void add(int x,int y,int z)
{
    graph *q=new graph;
    q->nod=y;
    q->cost=z;
    q->next=a[x];
    a[x]=q;
}
void read()
{
    f>>n>>m;
    int x,y,z,i;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        add(x,y,z);
    }
}
void upheap(int x)
{
    int t;
    while(x>1)
    {
        t=x>>1;
        if(d[h[t]]>d[h[x]])
        {
            poz[h[x]]=t;
            poz[h[t]]=x;
            swap(h[t],h[x]);
            x=t;
        }
        else return;
    }
}
void downheap(int x)
{
    int var;
    while(x<=k)
    {
        var=x;
        if((x<<1)<=k)
        {
            var=x<<1;
            if(var+1<=k )
                if(d[h[var+1]]<d[h[var]]) var++;
        }
        else return;
        if(d[h[x]]>d[h[var]])
        {
            poz[h[x]]=var;
            poz[h[var]]=x;
            swap(h[x],h[var]);
            x=var;
        }
        else
            return;
    }
}
void dijkstra_heap()
{
    int i,minn;
    fill(d+2,d+n+1,INF);
    fill(poz+2,poz+n+1,-1);
    poz[1]=1;
    h[++k]=1;
    while(k)
    {
        minn=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        k--;
        downheap(1);
        graph *q=a[minn];
        while(q)
        {
            if(d[q->nod]>d[minn]+q->cost)
            {
                d[q->nod]=d[minn]+q->cost;
                if(poz[q->nod]!=-1)
                    upheap(poz[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->next;
        }
    }
}
int main()
{
    read();
    dijkstra_heap();
    for(int i=2;i<=n;i++)
        if(d[i]==INF) g<<0<<' ';
        else g<<d[i]<<' ';

    return 0;
}