#include<bits/stdc++.h>
#define INF 10000000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,d[50002],heap[50002],poz[50002],n_heap;
vector< pair<int,int> >v[50002];

void upheap(int x)
{
    while(x>1 && d[heap[x]]<d[heap[x/2]])
    {
        swap(heap[x],heap[x/2]);
        swap(poz[heap[x]],poz[heap[x/2]]);
        x/=2;
    }
}

void removee()
{
    heap[1]=heap[n_heap];
    poz[heap[1]]=1;
    heap[n_heap]=0;
    n_heap--;
    int c=2,p=1;
    while(c<=n_heap)
    {
        if(c+1<=n_heap && d[heap[c+1]]<d[heap[c]])
            c++;
        if(d[heap[c]]<d[heap[p]])
        {
            swap(heap[c],heap[p]);
            swap(poz[heap[c]],poz[heap[p]]);
        }
        p=c;
        c=p*2;
    }
}

int main()
{
    int i,x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++)
    {
        d[i]=INF;
        heap[i]=i;
        poz[i]=i;
    }
    d[1]=0;
    n_heap=n;
    while(n_heap!=0)
    {
        int i=heap[1];
        removee();
        for(auto it:v[i])
        {
            int z=it.first;
            int p=it.second;
            if(d[z]>d[i]+p)
            {
                d[z]=d[i]+p;
                upheap(poz[z]);
            }
        }
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}