#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <fstream>
// PENTRU SET SE FOLOSESC PQ.BEGIN(), PQ.INSERT(P), PQ.ERASE(P)
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
set<pair<int,int>> pq;
const int INF = 1e6;
int n, m;
void Dijkstra(int s, vector<vector<pair<int,int>>> &adj, vector<int>& dist) {
    dist[s]=0;
    vector<int>viz(n+1,0);
    pq.insert({dist[s],s});
    while (pq.size() != 0) {
        auto p = pq.begin();
        int nod = p->second;
        int cost = p->first;
        pq.erase(p);
        if (viz[nod]==1) continue;
        viz[nod]=1;
        for (auto& m : adj[nod]) {
            int nod_m = m.first;
            int cost_m = m.second;
            if (dist[nod_m] > dist[nod] + cost_m) {
                pq.erase({dist[nod_m],nod_m});
                dist[nod_m] = dist[nod] + cost_m;
                pq.insert({dist[nod_m],nod_m});
            }
        }
    }
}
int main() {
    fin>>n>>m;
    vector<vector<pair<int,int>>> adj;
    vector<int> dist(n+1,INF);
    adj.resize(n+1);
    for (int i=1;i<=m;i++) {
        int a, b, c;
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    Dijkstra(1,adj,dist);
    for (int i=2;i<=n;i++) {
        if (dist[i]==INF) fout<<0<<" ";
        else fout<<dist[i]<<" ";
    }
    return 0;
}