#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define DIM 100005
#define INF DIM*10

using namespace std;

vector<pair<int, int>> listaAdiacenta[DIM]; 
set<pair<int, int>> q;
int dist[DIM], x, y, c;
int nr_varfuri, nr_muchii, k;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int main()
{
    fin >> nr_varfuri >> nr_muchii;
    for (int i = 1; i <= nr_muchii; i++)
    {
        fin >> x >> y >> c; 
        listaAdiacenta[x].push_back(make_pair(y, c));
    }

    for (int i = 1; i <= nr_varfuri; i++)
    {
        dist[i] = INF;
    }

    dist[1] = 0;

    q.insert(make_pair(0, 1)); 

    while (!q.empty()) 
    {
        int vertex = q.begin()->second; 
                                               
        q.erase(q.begin());             

        for (size_t i = 0; i < listaAdiacenta[vertex].size(); i++) 
        {
            int neighbour = listaAdiacenta[vertex][i].first; 
            int cost = listaAdiacenta[vertex][i].second;   

            if (dist[neighbour] > dist[vertex] + cost)  
            {
                q.erase(make_pair(dist[neighbour], neighbour)); 
                dist[neighbour] = dist[vertex] + cost;      
                q.insert(make_pair(dist[neighbour], neighbour));   

               
            }
        }
    }
    for (int i = 2; i <= nr_varfuri; i++) 
    { if (dist[i] == INF)
            fout << "0 ";        
        else
            fout << dist[i] << " ";
    }
}