#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>

#define nmax 50001
#define infinit 0x3f3f3f
using namespace std;


int n;

vector<pair<int, int> > graf[nmax]; /**graf[i].first - cost graf[i].second - catre nodul i*/
int d[nmax];
bool viz[nmax];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > coada;

void citire()
{
    int m;
    scanf("%d %d\n", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        scanf("%d %d %d\n", &x, &y, &cost);
        graf[x].push_back(make_pair(cost, y));

    }
}



void dijkstra()
{
    coada.push(make_pair(0, 1));
    while(!coada.empty())
    {
        int cost, nod;
        cost = coada.top().first;
        nod = coada.top().second;
        coada.pop();
        for(vector<pair<int, int> >::iterator it = graf[nod].begin(); it != graf[nod].end(); ++it)
        {
            if(d[it->second] > d[nod] + it->first)
                d[it->second] = d[nod]  + it->first;
            if(!viz[it->second])
            {
                coada.push(make_pair(d[it->second], it->second));
                viz[it->second] = true;
            }
        }
    }
}


void afisare()
{
    for(int i = 2; i <= n; i++)
        if(d[i] != infinit)
            cout << d[i] << ' ';
        else
            cout << infinit;
}


int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    citire();
    for(int i = 2; i <= n; i++)
        d[i] = infinit;
    dijkstra();
    afisare();
    return 0;
}