#include <fstream>
#include <iostream>
#include <vector>
#define maxn 50010
#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<pair<int,int> > vecini[maxn];
 vector<pair<int,int> >::iterator it;
 pair<int,int> temp;
inline void swap(int i, int j){
int z;

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

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

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