#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;
    
    set <pair<int, int> > s;
    
    dist[nod] = 0;
    
    s.insert({0, nod});
    while (s.empty() == 0)
    {
        nod1 = s.begin()->second;
        s.erase(s.begin());
        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;
                    s.insert({-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;
}