//Include
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
 
//Definitii
#define edge pair<int, int>
#define cost first
#define node second
 
#define pb push_back
#define mp make_pair
 
//Constante
const int MAX_SIZE = (int)5e4+1;
const int oo = (1<<30) - 1;
 
//Variabile
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
 
int nodes, edges;
 
vector<edge> graph[MAX_SIZE];
vector<edge>::iterator it, end;
 
vector<int> dist(MAX_SIZE, oo);
 
priority_queue<edge, vector<edge>, greater<edge> > heap;
 
//Main
int main()
{
    in >> nodes >> edges;
    int cFrom, cTo, cCost;
    while(edges--)
    {
        in >> cFrom >> cTo >> cCost;
        graph[cFrom].pb(mp(cCost, cTo));
    }
     
    heap.push(mp(0, 1));
    dist[1] = 0;
     
    while(!heap.empty())
    {
        int current = heap.top().node;
		if(dist[current] != heap.top().first)
		{
			heap.pop();
			continue;
		}
		
        heap.pop();
         
        end = graph[current].end();
        it = graph[current].begin();
        for(; it!=end ; ++it)
        {
            if(dist[current] + it->cost < dist[it->node])
            {
                dist[it->node] = dist[current] + it->cost;
                heap.push(mp(dist[it->node], it->node));
            }
        }
    }
     
    for(int i=2 ; i<=nodes ; ++i)
        out << (dist[i]==oo? 0 : dist[i]) << ' ';
     
     
    in.close();
    out.close();
    return 0;
}