#include <fstream>
#include <iostream>
#include <queue>
#include <utility>

#define pp pair<int,int>

using namespace std;

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

const int MaxN = 50001;
const int INF = 1 << 30;

vector < pair < int , int > > G[MaxN];// pair.first este nodu pair.second este costul pana la nod
int d[MaxN],n,m;//distante
bool inQ[MaxN];

int main()
{
    int x,y,c;

    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
       // G[y].push_back(make_pair(x,c));
    }


    int source = 1;
    inQ[source] = true;

    priority_queue < int, vector < int > ,greater< int > > pq; //primu parametru tipu de date; al doilea structura pe care se face pq - ul; al 3 - lea pastrea prop de MIN heap

    for(int i = 2;i <= n; i++) d[i] = INF;// setez distantele pana la INF
    d[source] = 0;//distanta din sursa e 0

    pq.push(source);// bag sursa si distana in heap

    while(!pq.empty())//cat mai e ceva in heap
    {
        int node = pq.top();//iau min-ul din heap adica nodu de la cre relaxex
        pq.pop();//eimin min-ul

        for(vector<pp>::iterator i = G[node].begin(); i != G[node].end(); ++i)//iteram prin toti vecinii
        {
            int newNode = i -> first;
            int newDistNode = i -> second;
            if(d[newNode] > d[node] + newDistNode)//daca putem relaxa
            {
                d[newNode] = d[node] + newDistNode;
                pq.push(newNode);//bagam in coada
            }
        }

    }

   for(int i = 2; i <= n; ++i)
        g << (d[i] < INF ? d[i] : 0) << " ";

    return 0;
}