#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

const int INF = 1e9;

struct edge
{
    int next, weight;
};

typedef pair<int, int> pii;

void dijkstra(int sn, int n, vector<vector<edge>> & adj)
{
    vector<int> dist(n + 1, INF);
    dist[sn] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, sn});
    while(!pq.empty()){
        auto [d, cn] = pq.top();
        pq.pop();
        if(d > dist[cn]) continue;
        for(edge &e : adj[cn]){
            auto [nn, w] = e;
            if(dist[cn] + w < dist[nn]){
                dist[nn] = dist[cn] + w;
                pq.push({dist[nn], nn});
            }
        }
    }
    for(int i = 2; i <= n; i++){
        if(dist[i] == INF) fout << 0 << ' ';
        else fout << dist[i] << ' ';
    }
}

int main()
{
    FASTIO
    
    int n, m; fin >> n >> m;
    vector<vector<edge>> adj(n + 1);
    for(int i = 1; i <= m; i++){
        int a, b, w; fin >> a >> b >> w;
        adj[a].push_back({b, w});
    }
    dijkstra(1, n, adj);
        
    return 0;
}