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

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

const int INF = 2000000000;
const int NMAX = 50005;
int n, m;
int dist[NMAX];
vector<pair<int, int>> G[NMAX]; 

void rezolva_dijkstra(int nod_start) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[nod_start] = 0;

    priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > Q;
    Q.push({0, nod_start});

    while (!Q.empty()) {
        int cost_curent = Q.top().first;
        int nod_curent = Q.top().second;
        Q.pop();

        if (cost_curent > dist[nod_curent]) {
            continue;
        }

        for (unsigned int i = 0; i < G[nod_curent].size(); i++) {
            int vecin = G[nod_curent][i].first;
            int cost_muchie = G[nod_curent][i].second;
            
            if (dist[vecin] > dist[nod_curent] + cost_muchie) {
                dist[vecin] = dist[nod_curent] + cost_muchie;
                Q.push({dist[vecin], vecin});
            }
        }
    }
}

int main() {
    fin >> n >> m;
    
    int nod1, nod2, cost;
    for (int i = 1; i <= m; i++) {
        fin >> nod1 >> nod2 >> cost;
        G[nod1].push_back({nod2, cost});
    }

    rezolva_dijkstra(1);

    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF) {
            fout << "0 ";
        } else {
            fout << dist[i] << " ";
        }
    }

    return 0;
}