#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

const int inf = 50000001;

int n, m;
vector <int> v[50002], c[50002];
queue <int> q;
int cost[50002];

void citeste () {
    f >> n >> m;
    int a, b, co;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> co;
        v[a].push_back (b);
        c[a].push_back (co);
        cost[i] = inf;
    }

    cost[1] = 0;
}

void rezolva () {
    q.push (1);
    int x;
    while (!q.empty ()) {
        x = q.front ();
        q.pop ();
        for (int i = 0; i < v[x].size (); i++)
            if (cost[v[x][i]] > cost[x] + c[x][i]) {
                cost[v[x][i]] = cost[x] + c[x][i];
                q.push (v[x][i]);
            }
    }

}

int main () {
    citeste ();
    rezolva ();
    for (int i = 2; i <= n; i++) g << cost[i] << ' ';
    g << '\n';
}