#include <bits/stdc++.h>
#include <cstdio>
#include <queue>

using  namespace std;

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

#define inf 1000000000

int n, m;
vector<pair<long long,int>> adj[50010];
bitset<50010> viz;
priority_queue<pair<long long, int>> pq;

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c; 
        adj[x].push_back({c, y});
    }
    
    vector<long long> dist(n + 1, inf);
    pq.push({0, 1});
    dist[1] = 0;

    while(!pq.empty())
    {
        int a = pq.top().second; pq.pop();
        if(viz[a]) continue;
        viz[a] = 1;
        for(auto x : adj[a])
        {
            long long b = x.second, w = x.first;
            if(dist[a] + w < dist[b])
            {
                dist[b] = dist[a] + w;
                pq.push({-dist[b], b});
            }
        }
    }

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

}