#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int Nmax = 50001;

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

int n, m;

priority_queue< pair<int, int> >  H; // maxheap - (cost, node)
bool visited[Nmax];
int d[Nmax];

void dijkstra(int source) {
    int i, x, y, cost;

    d[source] = 0;
    H.push({d[source], source});

    while (!H.empty()) {
        // verific daca in heap sunt noduri vizitate
        while(!H.empty() && visited[H.top().second]) {
            H.pop();
        }

        if (H.empty()) {
            break;
        }

        x = H.top().second;
        visited[x] = true;

        // parcurg vecinii y ai lui x
        for (i = 0; i < graph[x].size(); i++) {
            y = graph[x][i].first;
            cost = graph[x][i].second;

            if (d[y] > cost + d[x] || d[y] == -1) {
                d[y] = cost + d[x];
                H.push({-d[y], y});
            }
        }
    }
}

int main()
{
    // G - graf orientat

    // Lista de vecini
    // 1: (2,1), (4, 2)
    // 2: (3, 2)
    // 3: (5, 6)
    // 4: (3, 4), (5, 3)
    // 5:

    int i, x, y, cost;

    in >> n; // numarul de noduri
    in >> m; // numarul de arce
    for (i = 1; i <= m; i++) {
        in >> x >> y >> cost; // 1 2 1
        graph[x].push_back({y, cost});  
    }

    // initializare cu INF a vectorului d
    for (i = 1; i <= n; i++) {
        d[i] = -1;
    }

    dijkstra(1);

    for (i = 2; i <= n; i++) {
        if (d[j] == -1){
            d[j] = 0;
        }
        out << d[i] << " ";
    }

    return 0;
}