#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
int n,m;
vector<vector<pair<int,int>>> graf;
vector<int> visited;
vector<int> dist;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct PairComp
{
    bool operator()(const pair<int,int>& p1, const pair<int,int>& p2) const
    {
        if (p1.second == p2.second)
            return p1.first > p1.second;
        else
            return p1.second > p2.second;
    }
};
void dijkstra()
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, PairComp> q;
    visited[1] = 1;
    for (int i = 0; i < graf[1].size(); i++)
        q.push(make_pair(graf[1][i].first, graf[1][i].second));
    while (!q.empty())
    {
        
        pair<int,int> curp = q.top();
        q.pop();
        if (visited[curp.first])
            continue;
        visited[curp.first] = 1;
        dist[curp.first] = curp.second;
        for (int i = 0; i < graf[curp.first].size(); i++)
        {
            int neighbour = graf[curp.first][i].first;
            int cost =  graf[curp.first][i].second;
            if (!visited[neighbour])
                q.push(make_pair(neighbour, curp.second + cost));
        }
    }
}
void afisare()
{
    for (int i = 2; i <= n; i++)
        out << dist[i] << " ";
}
int main()
{

    in >> n >> m;
    graf.resize(n+1);
    visited.resize(n+1, 0);
    dist.resize(n+1, 0);
    for (int i = 0; i < m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        graf[x].push_back(make_pair(y,c));
    }
    dijkstra();
    afisare();
    

}