// the return
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

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

const int INF = 2e9;
const int N = 5e4;

vector <pair <int, int>> g[5 + N];
int dp[5 + N];
bool viz[5 + N];
int n, m;

priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;

int main() {
    //freopen("dijkstra.in", "r", stdin);
    //freopen("dijkstra.out", "w", stdout);
    in >> n >> m;
    //scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++) dp[i] = INF;
    for(int i = 1; i <= m; i++) {
        int x, y, cost;
        in >> x >> y >> cost;
        //scanf("%d%d%d", &x, &y, &cost);
        g[x].push_back(make_pair(cost, y));
    }

    dp[1] = 0;
    heap.push(make_pair(0, 1));

    while(heap.size()) {
        pair <int, int> top = heap.top();
        heap.pop();

        if(viz[top.second] == false) {
            viz[top.second] = true;
            for(auto to : g[top.second]) {
                if(dp[to.second] > to.first + dp[top.second]) {
                    dp[to.second] = to.first + dp[top.second];
                    heap.push(make_pair(dp[to.second], to.second));
                }
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        if(dp[i] != INF)
            out << dp[i] << " ";
        //printf("%d ", dp[i]);
        else out << "0 "; //printf("0 ");
    }
    out << '\n';
    //printf("\n");

    in.close();
    out.close();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}