#include <fstream>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
 
int dist[50001], n, f[50001], m;
 
vector <pair <int, int>> l[50001];
 
void dijkstra(int nod)
{
    int cost, i, nod1, nod2;
    for (i = 1; i<= n; i++)
        dist[i] = 1e9;
 
    priority_queue<pair<int, int> > dist_min;
 
    dist[nod] = 0;
 
    dist_min.push({0, nod});
    while (dist_min.size() > 0)
    {
        nod1 = dist_min.top().second;
        dist_min.pop();
        if(f[nod1] == 0)
        {
            f[nod1] = 1;
            for (i = 0; i < l[nod1].size(); i++)
            {
                nod2 = l[nod1][i].first;
                cost = l[nod1][i].second;
                if (dist[nod1] + cost < dist[nod2])
                {
                    dist[nod2] = dist[nod1] + cost;
                    dist_min.push({-dist[nod2], nod2});
                }
            }
        }
    }
}
 
int main()
{
    int x, y, cost, i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        l[x].push_back({y, cost});
    }
    
    dijkstra(1);
    
    for (i = 2; i<= n; i++)
        if(dist[i] == 1e9)
            fout << "0 ";
    else
        fout << dist[i] << " ";
    return 0;
}