#include <vector>
#include <fstream>
#include <queue>
#include <iostream>
#include <cstring>
#define nmax 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
typedef pair<int,int> pii;
int dist[nmax],n,m;
vector<pii> adj[nmax];
void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pii,vector<pii>,greater <pii> >pq;

    pq.push({dist[start],start});
    while(!pq.empty()) {
        int cost=pq.top().first;
        int node=pq.top().second;
        pq.pop();

        if (cost<=dist[node]) {
            for(int i=0;i<adj[node].size();i++) {
                int new_node=adj[node][i].first;
                int new_cost=adj[node][i].second;

                if (dist[new_node]>dist[node]+new_cost) {
                    dist[new_node]=dist[node]+new_cost;
                    pq.push({dist[new_node],new_node});
                }

            }
        }
    }
}
int main() {
    ///citire
    f>>n>>m;
    for (int i=0;i<m;i++) {
        int x,y,w;
        f>>x>>y>>w;
        adj[x].push_back({y,w});
    }
    for (int i=2;i<=n;i++) dist[i]=INT_MAX;
    dijkstra(1);
    for (int i=2;i<=n;i++) {
        if (dist[i]==INT_MAX) g<<0<<' ';
        else g<<dist[i]<<' ';
    }
    return 0;
}