#include <bits/stdc++.h>
	
 
	
using namespace std;
	
 
	
int n,m;
	
list<pair<int,int>> graf[50005]; //lista de adiacenta
	
        //cost,dst      //src
	
int distante[50005];
	
int viz[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 = numeric_limits<int>::max();
	
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;
	
        viz[u]=1;
	
        //iterez prin vecinii lui u
	
        for(auto &x:graf[u])
	
        {
	
            int weight = x.first;
	
            int v = x.second;
	
            if(!viz[v] && distante[v] > distante[u] + weight)
	
            {
	
                distante[v] = distante[u] + weight;
	
                pq.push(make_pair(-distante[v],v)); //pq e max heap
	
            }
	
        }
	
 
	
    }
	
    for(int i=2;i<=n;i++)
	
    {
	if (distante[i] == INF) {
            distante[i] = 0;
        }
        g<<distante[i]<<' ';
	
    }
	
}