#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;
vector <int> G[nmax];
vector <int> C[nmax];
struct
cmp{
    bool operator()(const int &a, const int &b) const
    {
        return d[a]<d[b];
    }
} ;


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[r] = 0;
    priority_queue <int, vector<int> , cmp> H; //heapu-ul , mentine structura de data sortata

    H.push(r);

    while(!H.empty())//cat timp mai avem nodui care pot imbunatati drumul de la r la un alt nod
    {
        x = H.top(); //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(int j = 0 ;j < C[x].size(); j++) //ameliorez drumurile, le imbunatatesc
        {

            y = G[x][j]; //nodul pentru care voi imbunatati drumul
            c = C[x][j] + 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(y) ;
            }
        }

    }

    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;
        G[x].push_back(y);
        C[x].push_back(dis);
      // T[x].push_back(Nod(y,dis));

    }

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

}