#include <fstream>
#include <iostream>
#include <vector>
#define maxn 50000
#define inf 123456789


using namespace std;

 int N,M, dist[maxn+100],poz[maxn+100], heap[maxn*5+100], hind, u,a ,b,c;
    vector<int> vecini[maxn],cost[maxn];
 vector<int>::iterator it,it1;

void swap(int i, int j)
{
int z;

    z=heap[i];
    heap[i]=heap[j];
    heap[j]=z;
    int t=poz[heap[i]];
    poz[heap[i]]=poz[heap[j]];
    poz[heap[j]]=t;

}
void upheap(int);
void add(int i) {
    heap[++hind]=i;
    upheap(hind);
    poz[i]=hind;
}
void downheap(int);
void dellete(int i) {
    poz[heap[i]]=-1;
    heap[i]=heap[hind];
    poz[heap[hind]]=i;
    heap[hind]=0;
    hind--;
    downheap(i);
}
void upheap(int i) {
    while (i/2>0&&dist[heap[i]]<dist[heap[i/2]])
    {
        swap(i,i/2);
        i/=2;
    }
}
void downheap(int i) {
    while ((2*i<=hind&&dist[heap[i]]>dist[heap[2*i]])||(2*i+1<=hind&&dist[heap[i]]>dist[heap[2*i+1]]))
    {
        if (2*i<=hind&&2*i+1>hind)
         {
             swap(i,2*i);
             i*=2;
         }
         else
        if (dist[heap[2*i+1]]<dist[heap[2*i]])
         {
             swap(2*i+1,i);
             i=2*i+1;
         }
         else
         {
             swap(2*i,i);
             i=2*i;
         }
    }
}
int main () {
    ifstream in;
    ofstream out;
    in.open("tests/grader_test10.in");
    out.open("dijkstra.out");
    in >> N >> M;
    int i=0;
    for (i=0; i<M; i++) {
       in >> a >> b>>c;
       vecini[a].push_back(b);
       cost[a].push_back(c);
    }
    dist[1]=0;
    add(1);
    for (i=2; i<=N; i++)
    {
        dist[i]=inf;
        add(i);
    }
    int v,alt;
    while (hind!=0) {
        u=heap[1];
       if (dist[u]==inf) break;
        dellete(1);

        for (it=vecini[u].begin(),it1=cost[u].begin();it!=vecini[u].end()&&it1!=cost[u].end();it++,it1++) {
            v=*it;
            alt=dist[u]+*it1;
            if (alt<dist[v]) {
                dist[v]=alt;
                if (poz[v]>0) {
                     upheap(poz[v]);
                }
            }
        }
    }
    for (i=2; i<=N; i++)
    {
        if (dist[i]==inf) dist[i]=0;
    out << dist[i] << " ";
    }
    out.close();
    return 0;
}