#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 2000000000

using namespace std;
int poz[50001],f[50001];
vector <pair <int,int> > v[250001];
pair <long long,int> h[50001];
int elem;
int d[50001];
void adauga (int val,int nod){
    int c,p;
    elem++;
    poz[nod]=elem;
    h[elem].first=val;
    h[elem].second=nod;
    c=elem;
    p=elem/2;
    while (p>0){
        if (h[c].first<h[p].first){
            swap (poz[h[c].second],poz[h[p].second]);
            swap (h[c],h[p]);
        }
        else break;
        c=p;
        p/=2;
    }
}
void sterge (){
    int c,p;
    h[1].first=h[elem].first;
    h[1].second=h[elem].second;
    poz[h[elem].second]=1;
    elem--;
    p=1;
    c=2;
    while (c<=elem){
        if (c+1<=elem && h[c+1].first<h[c].first)
            c++;
        if (h[c].first<h[p].first){
            swap (poz[h[c].second],poz[h[p].second]);
            swap (h[c],h[p]);
        }
        else break;
        p=c;
        c*=2;
    }
}
void update (int nod){
    int po,c,p;
    po=poz[nod];
    // po = pozitia nodului pe care l-am updatat in heap
    c=po;
    p=po/2;
    while (p>0){
        if (h[c].first<h[p].first){
            swap (poz[h[c].second],poz[h[p].second]);
            swap (h[c],h[p]);
        }
        else break;
        c=p;
        p/=2;
    }
}
int main()
{
    FILE *fin=fopen ("dijkstra.in","r");
    FILE *fout=fopen ("dijkstra.out","w");
    int n,m,i,nod,vecin,x,y,z;
    int mini,cost;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&z);
        v[x].push_back (make_pair (y,z) );
    }
    // h.first = valoare
    // h.second = nodul
    // poz[nod] = pe ce poz se afla nodul nod in heap
    adauga (0,1);
    for (i=2;i<=n;i++)
        adauga (INF,i);
    for (;;){
        nod=h[1].second;
        mini=h[1].first;
        if (mini==INF)
            break;
        //printf ("%d %lld\n",nod,mini);
        sterge ();
        d[nod]=mini;
        f[nod]=1;
        for (vector <pair <int,int> > :: iterator it=v[nod].begin() ; it!=v[nod].end() ; it++){
            vecin=it->first;
            cost=it->second;
            if (f[vecin]==0 && cost+mini<h[poz[vecin]].first){
                h[poz[vecin]].first=cost+mini;
                update (vecin);
            }
        }
        if (elem<=0)
            break;
    }
    for (i=2;i<=n;i++){
        if (d[i]==INF)
            d[i]=0;
        fprintf (fout,"%d ",d[i]);
    }
    return 0;
}