#include<bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int INF = 1e9;
struct Nod
{
    int nr, cost;
    Nod(int nr, int cost)
    {
        this -> nr = nr;
        this -> cost = cost;
    }
};
vector<Nod> graf[50005];
vector<int> dist(50005, INF);
int n, m;
void citire()
{
    in>>n>>m;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x, y, c;
        in>>x>>y>>c;
        Nod nod = Nod(y, c);
        graf[x].pb(nod);
    }
}
class cmp{
public:
    bool operator()(Nod a, Nod b)
    {
        return a.cost < b.cost;
    }
};
void dijkstra(int start)
{
    priority_queue<Nod, vector<Nod>, cmp > pq;
    Nod aux = Nod(start, 0);
    pq.push(aux);
    dist[start] = 0;
    while ( !pq.empty() )
    {
        Nod nod = pq.top();
        pq.pop();
        for ( Nod vecin : graf[nod.nr] )
        {
            if ( dist[vecin.nr] > dist[nod.nr] + vecin.cost )
            {
                dist[vecin.nr] = dist[nod.nr] + vecin.cost;
                pq.push(vecin);
            }
        }
    }
}
void afisare()
{
    for ( int i = 2 ; i <= n ; i++ )
    {
        if ( dist[i] == INF )
        {
            out<<0<<" ";
        }
        else
        {
            out<<dist[i]<<" ";
        }
    }
}
int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}