#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int NMAX = 50000;
const int INF = (1 << 30);

int distanta[NMAX + 5];
bool in_coada[NMAX + 5];
int n, m;

vector <pair <int, int> > muchii[NMAX + 5];

struct compara_distante
{
    bool operator()(int x, int y)
    {
        return distanta[x] > distanta[y];
    }
};

priority_queue <int, vector<int>, compara_distante> coada;
///primul obiect este cel care construieste coada, al doilea parametru este o structura in care adunam toate obiectele intr-un vector, o functie care sa ordoneze min si max

void Dijkstra_algorithm(int node_start)
{
    for(int i = 1; i <= n; i++)
    {
        distanta[i] = INF;
    }

    distanta[node_start] = 0;
    coada.push(node_start);
    in_coada[node_start] = true; ///marcat ca fiind in coada

    while(!coada.empty())
    {
        int current_node = coada.top(); ///extragem nodul curent
        coada.pop(); ///il eliminam
        in_coada[current_node] = false; ///marcam ca nu se mai afla in coada

        for(unsigned int i = 0; i < muchii[current_node].size(); i++)
        {
             int neighbour = muchii[current_node][i].first;
             int cost = muchii[current_node][i].second;

             if(distanta[current_node] + cost < distanta[neighbour])
             {
                distanta[neighbour] = distanta[current_node] + cost;

                if(in_coada[neighbour] == false) ///daca vecinul nu se afla in coada
                {
                    coada.push(neighbour); ///il vom pune in coada
                    in_coada[neighbour] = true; ///marcam ca se afla in coada
                }
             }
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        muchii[x].push_back(make_pair(y, cost));
    }

    Dijkstra_algorithm(1);

    for(int i = 2; i <= n; i++)
    {
        if(distanta[i] != INF)
        {
            out << distanta[i] << " ";
        }
        else
        {
            out << "0 ";
        }
    }
    in.close();
    out.close();
    return 0;
}