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

using namespace std;

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

bool inQ[50005];
queue<int> Q;
vector<pair<int, int> > graph[50005];
int n, m, dist[50005];

void citire() {
    f >> n >> m;
    for (int i = 1; i <= n; i++)
        dist[i] = INT_MAX / 4 - 1;
    dist[1] = 0;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        graph[x].emplace_back(y, c);
    }
}

void rezolvare() {
    Q.push(1);
    inQ[1] = 1;
    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        for (auto &v:graph[nod]) {
            if (dist[v.first] > dist[nod] + v.second) {
                dist[v.first] = dist[nod] + v.second;
                if(!inQ[v.first]){
                    Q.push(v.first);
                    inQ[v.first]=1;
                }

            }
        }
    }

    for(int i=2; i<=n; i++)
        g<<dist[i]<<" ";
}

int main() {
    citire();
    rezolvare();
    return 0;
}