#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <set>

using namespace std;

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

const int NMax = 50005;
const int INF = 1e9;

int n;
int D[NMax];

set < pair < int, int > > T;
vector < int > G[NMax], C[NMax];

void dijkstra(){
    int val, node;
    for(int i = 2; i <= n; i++){
        D[i] = INF;
    }
    T.insert(make_pair(1, 0));
    while(!T.empty()){
        node = (*T.begin()).first;
        val = (*T.begin()).second;
        T.erase(T.begin());
        for(int i = 0; i < G[node].size(); i++){
            if(D[G[node][i]] > val + C[node][i]){
                D[G[node][i]] = val + C[node][i];
                T.insert(make_pair(G[node][i], D[node][i]));
            }
        }
    }
}

int main(){
    int m, a, b, c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> a >> b >> c;
        G[a].push_back(b);
        C[a].push_back(c);
    }
    dijkstra();
    for(int i = 2; i <= n; i++){
        if(D[i] == INF){
            fout << 0 << " ";
        } else {
            fout << D[i] << " ";
        }
    }
    return 0;
}