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

#define Nmax 50001 
#define INF 1000000001 // 1e9+1
using namespace std;

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

vector <pair<int, int> > graph[Nmax];

int d[Nmax];
queue <int> q;

int main()
{
    int N, M, i, j, x, y, c;

    in >> N; // numarul de noduri
    in >> M; // numarul de muchii

    for (i = 1; i <= M; i++) {
        in >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
    }

    // afisare liste de vecini
    // for (i = 1; i <= N; i++) {
    //     cout << i << ": ";
    //     // afisare vecini pentru nodul i
    //     for (j = 0; j < graph[i].size(); j++) {
    //         cout << "[" << graph[i][j].first << " " << graph[i][j].second << "]; ";
    //     }
    //     cout << '\n';
    // }

    // initializare vector d cu INF
    for (i = 1; i <= N; i++) {
        d[i] = INF;
    }

    // sursa este nodul 1
    d[1] = 0;
    // inserez in coada nodul de start
    q.push(1);

    while(!q.empty()) {
        x = q.front(); // extragere element de la inceputul cozii
        q.pop(); // eliminare element de la inceputul cozii

        for (i = 0; i < graph[x].size(); i++) {
            y = graph[x][i].first;
            c = graph[x][i].second;
            // x y c
            if (d[y] > d[x] + c) {
                d[y] = d[x] + c;
                // inserez in coada y
                q.push(y);
            }
        }
    }

    // afisare vector de distante d
    for (int i = 2; i <= N; i++) {
        if (d[i] == INF) {
            d[i] = 0;
        }
        out << d[i] << " ";
    }
    out << '\n';

    return 0;
}