#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int s = 1, nr_varfuri, nr_arce, cm[50002], viz[50002], infinit = 100000000;
vector <pair<int, int>>vec[50002];

void citire()
{
    ifstream f("dijkstra.in");
    f >> nr_varfuri >> nr_arce;
    for(int i=1; i<=nr_arce; i++)
    {
        int u, v, cost;
        f >> u >> v >> cost;
        vec[u].push_back(make_pair(v, cost));
    }
}

void dijkstra()
{
    ofstream g("dijkstra.out");
    queue <int> q;
    q.push(s);
    for(int i=1; i<=nr_varfuri; i++)
        cm[i] = infinit;
    cm[s] = 0;
    while(!q.empty())
    {
        int u = q.front();
        if(!u)
            break;
        q.pop();
        int minim = infinit, nod_min = 0;
        for(int i=1; i<=nr_varfuri; i++)
            if(!viz[i] && cm[i] <= minim)
            {
                minim = cm[i];
                nod_min = i;
            }
        for(int i=0; i<vec[u].size(); i++)
            if(!viz[vec[u][i].first] && cm[u] + vec[u][i].second < cm[vec[u][i].first])
                cm[vec[u][i].first] = cm[u] + vec[u][i].second;
        q.push(nod_min);
        viz[u] = 1;
    }
    for(int i=2; i<=nr_varfuri; i++)
        g << cm[i] << " ";
}

int main()
{
    citire();
    dijkstra();

    return 0;
}