#include<fstream>
#include<iostream>
#include<vector>
#define inf 800000
using namespace std;

vector <pair <int,int> > v[50001];
int N,M,dist[50001],h[50001],poz[50001],k;

void citire() {

    ifstream in("dijkstra.in");
    int x,y,c,i;
    in>>N>>M;
    for(i=1;i<=M;i++){
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    in.close();

}

void downheap(int nod) {

    int fiu;
    while(nod<=k) {
        fiu=nod;
        if(nod*2<=k) {
            fiu=nod*2;
            if(fiu+1<=k)
                if(dist[h[fiu+1]]<dist[h[fiu]])
                    fiu++;
        }
        else
            return;

        if(dist[h[nod]]>dist[h[fiu]]) {
            poz[h[nod]]=fiu;
            poz[h[fiu]]=nod;
            swap(h[nod],h[fiu]);
            nod=fiu;
        }
        else
            return;

    }
}

void upheap(int nod) {

    int tata;
    while(nod>1) {
        tata=nod/2;
        if(dist[h[tata]]> dist[h[nod]]) {
            poz[h[tata]]= nod;
            poz[h[nod]]= tata;
            swap(h[tata],h[nod]);
            nod=tata;
        }
        else
            nod=1;
    }

}

void solve() {

    int i,vecin,nod,cost;

    for(i=2;i<=N;i++) {
        dist[i]=inf;
        poz[i]=-1;
    }
    poz[1]=1;
    h[++k]=1;

    while(k) {
        nod=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        k--;
        downheap(1);
        for(i=0;i<v[nod].size();i++){
            vecin=v[nod][i].first;
            cost=v[nod][i].second;
            if(dist[vecin]>dist[nod]+cost) {
                    dist[vecin]=dist[nod]+cost;
                    k++;
                    h[k]=vecin;
                    poz[vecin]=k;
                    upheap(k);
                    }
            }
    }

}


void afisare() {

    ofstream out("dijkstra.out");
    int i;
    for(i=2;i<=N;i++){
        if(dist[i]==inf)
            out<<0<<' ';
        else
            out<<dist[i]<<' ';
    }
    out<<'\n';
    out.close();

}

int main() {

    citire();
    solve();
    afisare();
    return 0;

}