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