#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int m, n, a, b, c;
int d[50001];
int initial, nod;

vector <pair<int,int> > lista[50001];
vector <pair<int,int> >::iterator it;
queue <int> coada;

void initializareDate()
{
    f >> n >> m;
    for(int i=1;i<=n;i++) d[i]=10000000000;
    for(int i=1;i<=m;i++)
    {
        f >> a >> b >> c;
        lista[a].push_back(make_pair(b,c));
    }
    initial=1;
    d[initial]=0;
}

void dijkstra()
{
    //pun nodul initial in coada si in vizitez
    coada.push(initial);
    /*cat timp coada nu este goala
    1. selectez un nod din coada, nevizitat si il extrag
    2. parcurg vecinii nodului din lista de adiacenta
    3. daca pot ajunge la vreunul din vecinii nodului curent prin intermediul nodului curent cu un cost mai bun
        atunci actualizez costul pentru nodul vecin
    4. daca vecinul nodului curent nu e vizitat, il vizitez si il adaug in coada
    */
    while(!coada.empty())
    {
        nod=coada.front();
        coada.pop();
        for(it=lista[nod].begin();it!=lista[nod].end();it++)
               if(d[nod]+it->second<d[it->first])
               {
                   d[it->first]=d[nod]+it->second;
                   coada.push(it->first);
               }
    }
}
void afisare()
{
    for(int i=2; i<=n; i++)
        if(d[i]!=10000000000) g << d[i] << " ";
        else g << 0 << " ";
}
int main()
{
    initializareDate();
    dijkstra();
    afisare();
    return 0;
}