#include<bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int d[50005];
struct cmp
{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};
struct nod
{
    int x, c;
};
vector<nod> g[50005];
int n, m;
void citire()
{
    in>>n>>m;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x, y, c;
        in>>x>>y>>c;
        nod a = {y, c};
        g[x].push_back(a);
    }
}
void rez()
{
    priority_queue<int, vector<int>, cmp> pq;
    pq.push(1);
    while ( !pq.empty() )
    {
        int nm = pq.top();
        pq.pop();
        for ( nod vec : g[nm] )
        {
            if ( d[vec.x] )
                continue;
            d[vec.x] = d[nm] + vec.c;
            pq.push(vec.x);
        }
    }
    for ( int i = 2 ; i <= n ; i++ )
    {
        out<<d[i]<<" ";
    }
}
int main()
{
    citire();
    rez();
    return 0;
}