/// Aceasta sursa este pentru problema
/// https://www.infoarena.ro/problema/dijkstra
/// Punctaj: 100
/// Grupa Medie (pt seniori)

#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>

#define DIM 50000
#define INF 1000000005

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

//ifstream f("in.in");
//ofstream g("out.out");

typedef pair<int,int> intPair;

int n,m,x,y,lung;
vector <pair<int,int>> l[DIM+5];
priority_queue <intPair,vector<intPair>,greater<intPair>> pq;
int D[DIM+5];
bool viz[DIM+5];

void dijkstra(int start){
    for(int i=1;i<=n;i++){
        D[i] = INF;
    }
    D[start] = 0;
    pq.push({0,start});
    while(!pq.empty()){
        int nod = pq.top().second;
        int lastLung = pq.top().first;
        pq.pop();

        if(lastLung != D[nod]){
            continue;
        }

        for(int i=0;i<l[nod].size();i++){
            int vec = l[nod][i].first;
            int lung = l[nod][i].second;

            if(D[vec] > D[nod] + lung){
                D[vec] = D[nod] + lung;
                pq.push({D[vec],vec});
            }
        }
    }
}

int main(){

    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>lung;
        l[x].push_back({y,lung});
    }

    dijkstra(1);

    for(int i=2;i<=n;i++){
        if(D[i] == INF){
            g<<0<<" ";
        }else{
            g<<D[i]<<" ";
        }
    }

    f.close();
    g.close();
    return 0;
}