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

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

struct comp
{
    bool operator()(pair<int, int> a,pair<int, int> b)
    {
        return a.second > b.second;
    }
};

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({v, cost});
    }
}

void dijkstra()
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, comp> nod;
    for(int i=2; i<=nr_varfuri; i++)
        cm[i] = infinit;
    nod.push({1, 0});

    while(!nod.empty())
    {
        int u = nod.top().first;
        nod.pop();
        viz[u] = 1;

        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;
                nod.push({vec[u][i].first, cm[vec[u][i].first]});
            }
    }

    ofstream g("dijkstra.out");
    for(int i=2; i<=nr_varfuri; i++)
        g << cm[i] << " ";
}

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

    return 0;
}