#include <bits/stdc++.h>

using namespace std;

int n,m;
list<pair<int,int>> graf[50005]; //lista de adiacenta
        //dst,cost      //src
int distante[50005];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

priority_queue<pair<int,int>> pq;
                   //cost,nod - scris asa ca sa nu mi fac functie comp
const int INF = 9999999;
int main()
{
    // citesc graf
    f>>n>>m;
    for(int i=0;i<m;i++){
        int src,dst,cost;
        f>>src>>dst>>cost;
        graf[src].push_back(make_pair(cost,dst));
    }


    // nod start dist 0, restul dist infinit
    distante[1] = 0;
    for(int i=2;i<=n;i++)
    {
        distante[i] = INF;
    }

    cout<<"\n";
    // incep cu nodu 1 cost 0
    pq.push(make_pair(0,1));

    while(!pq.empty())
    {
        auto src = pq.top();
        pq.pop();
        int u = src.second;
        //iterez prin vecinii lui u
        for(auto &x:graf[u])
        {
            int weight = x.first;
            int v = x.second;
            if(distante[v] > distante[u] + weight)
            {
                distante[v] = distante[u] + weight;
                pq.push(make_pair(distante[v],v));
            }
        }

    }
    for(int i=2;i<=n;i++)
    {
        g<<distante[i]<<' ';
    }
}