//Dragan Andrei Gabriel
//Universitatea din Bucuresti

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;


priority_queue< pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > Coada;
vector < pair <int,int> > Muchii[50001];
int Cost[50001], Nod, n, m, x, y, cost;

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d",&n, &m);

    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &x, &y, &cost);
        Muchii[x].push_back(make_pair(y, cost));
    }

    for(int i = 1; i <= n; i++)
        Cost[i] = LONG_MAX;

    Coada.push(make_pair(0, 1));
    Cost[1]=0;

    while(!Coada.empty())
    {
        cost = Coada.top().first;
        Nod = Coada.top().second;
        Coada.pop(); // scoatem muchia de cost minim
        for(vector < pair <int, int> >:: iterator it = Muchii[Nod].begin(); it != Muchii[Nod].end(); it++)
        {
            if(Cost[it -> first] > cost + it -> second)
            {
                Cost[it -> first] = cost + it -> second;
                Coada.push(make_pair(Cost[it -> first], it -> first));
            }
        }

    }
    for(int i = 2; i <= n; i++)
        printf("%d ", Cost[i] == LONG_MAX ? 0 : Cost[i]);
    return 0;
}