#include <iostream>
#include <fstream>
#define NMAX 50005
#define inf (1 << 30)
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct dijkstra
{
    int nod,cost;
    dijkstra *next;
}*a[NMAX],*q;
void add(int nod1,int nod2,int cost)
{
    dijkstra *q=new dijkstra;
    q->cost=cost;
    q->nod=nod2;
    q->next=a[nod1];
    a[nod1]=q;
}
int n,m,dist[NMAX],heap[NMAX],pos[NMAX];
void read()
{
    f>>n>>m;
    int x,y,d;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>d;
        add(x,y,d);
    }
}
void schimb(int x,int y){swap(pos[heap[x]],pos[heap[y]]); swap(heap[x],heap[y]);}
void heapup(int i)
{
    if(dist[heap[i/2]]<dist[heap[i]]||i==1)return;
    schimb(i,i/2);
    heapup(i/2);
}
void heapdown(int i)
{
    if(i*2>m)return;
    int st=dist[heap[2*i]],dr;
    if(i*2+1<=m)dr=dist[heap[2*i+1]]; else dr=st+1;
    if(min(st,dr)<dist[heap[i]])
        if(st<dr)
        {
            schimb(i,2*i);
            heapdown(2*i);
        }
        else
        {
            schimb(i,2*i+1);
            heapdown(2*i+1);
        }
}
void solve()
{
    for(int i=2; i<=n; i++)dist[i]=inf,pos[i]=-1;
    m=1; heap[1]=1; dist[1]=0; pos[1]=1;
    while(m)
    {
        int MIN=heap[1];
        schimb(1,m);
        --m; heapdown(1);
        q=a[MIN];
        while(q)
        {
            if(dist[q->nod]>dist[MIN]+q->cost)
            {
                dist[q->nod]=dist[MIN]+q->cost;
                if(pos[q->nod]!=-1)
                    heapup(pos[q->nod]);
                else
                {
                    heap[++m]=q->nod;
                    pos[heap[m]]=m;
                    heapup(m);
                }
            }
            q=q->next;
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]==inf)
        g<<0<<" ";
    else
        g<<dist[i]<<" ";
}
int main()
{
    read();
    solve();
    return 0;
}