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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF=INT_MAX;
vector<pair<int,int>> ad_ponderat[50005];
vector<int> d(50005, INF);
int N,M;

void citire(){
    fin>>N>>M;
    for(int i=1;i<=M;i++){
        int A,B,C;
        fin>>A>>B>>C;
        ad_ponderat[A].push_back({B,C});
    }
}

void dijkstra(int start){
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    d[start]=0;
    pq.push({0, start});
    while(!pq.empty()){
        int x=pq.top().second;
        pq.pop();
        for(int i=0;i<ad_ponderat[x].size();i++){
            pair nod=ad_ponderat[x][i];
            int cost=nod.second;
            int nr_nod=nod.first;
            if(d[x]+ cost<d[nr_nod]){
                d[nr_nod]=d[x]+ cost;
                pq.push({d[nr_nod], nr_nod});
            }
        }

    }
}


int main()
{
    citire();
    dijkstra(1);
    for(int i=2;i<=N;i++){
        if(d[i]==INF) fout<<0<<" ";
        else fout<<d[i]<<" ";
    }
    return 0;
}