#include <bits/stdc++.h>
#include <limits>

using namespace std;

int infinit = std::numeric_limits<int>::max();

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

vector<pair<int,int>> costuri[100001];
bool V[100001];
int dist[100001];

void dijkstra()
{
    dist[1]=0;

    priority_queue<pair<int,int>> H; /// Va sorta singur in functie de cea mai mica distanta
    H.push({0,1});

    while(H.size() > 0)
    {

        int u = H.top().second;
        H.pop();


        for(auto v : costuri[u]) /// Verificam toti vecinii lui u
        {
            if(dist[v.first] > dist[u] + v.second)
            {
                dist[v.first] = dist[u] + v.second;
                H.push({dist[v.first], v.first});
            }
        }
    }
}

int main()
{
    int nr_N,nr_M;
    in >> nr_N >> nr_M;

    for(int i = 1; i <= nr_M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        costuri[x].push_back({y,c}); /// Muchia de la x plecand in y are costul c
    }

    for(int i = 1; i <= nr_N; i++)
        dist[i] = infinit;

    dijkstra();

    for(int i = 2; i <= nr_N; i++)
    {
        if(dist[i] != infinit)
            out << dist[i] << " ";
        else
            out << "0 ";
    }
    return 0;
}