#include<fstream>
#include<vector>
#include<cstring>
#include<queue>

#define nmax 50020
#define oo 10000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

bool s[nmax];//vizitarea nodurilor intermediare
int d[nmax], n, m  ;//distnta minima de la nodul r la nodul indice
int x,y,dis;
struct
Nod{
    int x, cost;
    Nod(int _x, int _cost)
    {
      x = _x;
      cost = _cost;
    }
    Nod()
    {
        x = 0; cost = 0;
    }
    bool operator <(const Nod &x) const
    {
        return cost>x.cost ;
    }
} ;
vector <Nod> T[nmax]; //graful

void dijkstra(int r)
{
    int i,y,c,x;
    for(int i = 0; i < nmax ;i++)
    d[i] = oo;
    memset(s, false, sizeof(s));
    d[1] = 0;
    priority_queue <Nod> H; //heapu-ul , mentine structura de data sortata

    H.push(Nod(1, 0));

    while(!H.empty())//cat timp mai avem nodui care pot imbunatati drumul de la r la un alt nod
    {
        x = H.top().x; //alegem nodul din coada cu costul cel mai mic pana la radacina
        H.pop();
//        if(s[x])//daca nu e vizitat
//            continue;
//        s[x] = true;
        //fout << x <<'\n';
        for(vector <Nod> :: iterator it = T[x].begin(); it!=T[x].end(); it++) //ameliorez drumurile, le imbunatatesc
        {

            y = it->x; //nodul pentru care voi imbunatati drumul
            c = it->cost + d[x]; //noul cost intermediar

            if(d[y] > c) //daca noul cost intermediar e mai bun decat cel gasi pana la momentul actual
            {

                d[y] = c;
                H.push(Nod(y,c) ) ;
            }
        }

    }

    for(int i = 2; i <= n;i++)
        if(d[i] == oo)
            fout <<"0" <<" ";
            else
        fout <<d[i] <<" ";

}
void read()
{
    int i;
    fin >> n >> m;

    for(i = 1; i <= m ;i++)
    {
        fin >>x >> y >>dis;
       T[x].push_back(Nod(y,dis));

    }

}
int main()
{
    read();
    dijkstra(1);
    fin.close();
    return 0;;

}