#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <list>
#include <algorithm>
 
#define Max 100001
#define Max2 50005
#define inf 1000000000
 
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
int N, M;
int D[Max2]; // D[i] – distanta minima intre nodul de start si nodul numarul i
bool queue_check[Max2];
 
vector <pair<int,int> >weighted_graph[Max2];
priority_queue <pair<int,int> >q;
 
class Graph{
private:
    int NumberOfNodes, NumberOfEdges;
    vector<int> adjacencyList[Max]; // lista de adiacenta
 
public:
    Graph(int N, int M); // constructor
    void Read_Dijkstra();
    void Dijkstra( int node );
    void Write_Dijkstra();
};
 
// constructor
Graph :: Graph(int N, int M)
{
    NumberOfNodes = N;
    NumberOfEdges = M;
}
 
void Graph :: Read_Dijkstra()
{
    for ( int i = 1; i <= NumberOfEdges; i++ )
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        weighted_graph[x].push_back(make_pair(cost, y));
    }
 
    // setam vectorul pe inf
    for ( int i = 1; i <= NumberOfNodes; i++ )
        D[i] = inf;
}
 
void Graph :: Dijkstra(int Start_node)
{   
    // distanta pana la nodul de start = 0
    D[Start_node] = 0;
 
    // Punem nodul de start in coada
    q.push(make_pair(0,Start_node));
    queue_check[Start_node] = 1;
 
    while ( !q.empty() )
    {
        // extragem nodul curent
        int node = q.top().second;
        q.pop();
 
        queue_check[node] = 0;
        for ( auto i : weighted_graph[node] )
        {
            int next = i.second;    // vecinul
            int cost = i.first;
            // daca gasim o distanta mai mica
            if ( D[node] + cost < D[next] )
            {
                D[next] = D[node] + cost;
                // daca vecinul nu se afla in coada il adaugam
                if ( queue_check[next] == 0 )
                {
                    queue_check[next] = 1;
                    q.push(make_pair(D[next],next));
                }
            }
        }
    }
}
 
void Graph :: Write_Dijkstra()
{
    for ( int i = 2; i <= NumberOfNodes; i++ )
    {
        if ( D[i] != inf )
            fout << D[i] << " ";
        else 
            fout << "0 ";
    }
}
 
int main()
{
    fin >> N >> M;
    Graph G(N, M);
    G.Read_Dijkstra();
    G.Dijkstra(1);
    G.Write_Dijkstra();
    
    return 0;
}