#include <iostream>
#include <fstream>
#include <climits>
#define NMAX 50005
#define inf INT_MAX
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(heap[x],heap[y]);
    swap(pos[heap[x]],pos[heap[y]]);
}
void heapup(int i)
{
    if(dist[heap[i/2]]<dist[heap[i]])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()
{
    int nod;
    for(int i=1; i<=n; i++)
    {
        dist[i]=inf;
        heap[i]=i;
        pos[i]=i;
    }
    m=n;
    dist[1]=0;
    dist[0]=-1;
    for(int i=1; i<=n; i++)
    {
        nod=heap[1]; schimb(1,m);
        m--; heapdown(1);
        for(q=a[nod];q!=NULL;q=q->next)
            if(dist[q->nod]>dist[nod]+q->cost)
        {
            dist[q->nod]=dist[nod]+q->cost;
            heapup(pos[q->nod]);
        }
    }
    for(int i=2;i<=n;i++)
        if(dist[i]==inf)
        g<<0<<" ";
    else
        g<<dist[i]<<" ";
}
int main()
{
    read();
    solve();
    return 0;
}