#include <bits/stdc++.h>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int nmax = 50000;
const int INF = 1000000000;
vector <pair<int, int>> vecini[nmax+5];
int distanta[nmax+5];
priority_queue <pair<int, int>, vector <pair<int, int>>, greater <pair<int, int>>> pq;

void calcul(int sursa, int n)
{
    int i;
    for(i = 2; i <= n; ++i)
    {
        distanta[i] = INF;
    }
    distanta[sursa] = 0;
    pq.push({distanta[sursa], sursa});
    ///pun sursa in coada
    while( !pq.empty()) ///mai am varfuri de vizitat
    {
        pair<int, int> p = pq.top();
        int dist = p.first;
        int nod = p.second;
        pq.pop(); ///il scot din coada
        if(dist == distanta[nod]) ///PENTRU TIMP!!!
        {
            for(auto p : vecini[nod])
            {
                int nodnou = p.first;
                int cost = p.second;
                if(distanta[nodnou] > dist + cost)
                {
                    distanta[nodnou] = dist + cost;
                    pq.push({distanta[nodnou], nodnou});
                }
            }
        }
    }
}

int main()
{
    int n, m, i, x, y, z;
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> z;
        vecini[x].push_back({y, z});
    }
    calcul(1, n);
    for(i = 2; i <= n; ++i)
    {
        if(distanta[i] == INF)
            g <<"0 ";
        else
            g << distanta[i] << " ";
    }
    return 0;
}