#include <bits/stdc++.h>

using namespace std;

#define maxx INT_MAX
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int noduri, muchii,x,y,c, dist[50001];
bool trecut[50001];
vector<vector<pair<int,int>>> adc;


void Dijkstra(int nod){
    priority_queue<pair<int,int>> pq;
    pq.push(make_pair(0,nod));
    dist[nod]=0;
    while(!pq.empty()){
        pair<int,int> top = pq.top();
        int c= -top.first;
        int n= top.second;
        pq.pop();
        if(trecut[n]) continue;
        trecut[n]=true;
        for(int i=0; i<adc[n].size(); i++){
                int vecin = adc[n][i].second;
                int cos = adc[n][i].first;
            if(dist[vecin]>dist[n]+cos){
                dist[vecin]=dist[n]+cos;
            }
            pq.push(make_pair(-dist[vecin],vecin));
        }
    }
}

int main()
{
    fin>>noduri>>muchii;
    adc.resize(noduri + 1);
    for(int i=0; i<muchii; i++){
        fin>>x>>y>>c;
        adc[x].push_back(make_pair(c,y));
        //adc[y].push_back(make_pair(c,x));
    }

    for(int i=2; i<=noduri; i++){
        dist[i]=maxx;
        trecut[i]=false;
    }
    Dijkstra(1);
    for(int i=2; i<=noduri; i++){
        if(dist[i]==maxx) fout<<0<<' ';
        else fout<<dist[i]<<' ';
    }
    return 0;
}