#include <fstream>

#include <vector>

#include <queue>

#define MAX 50100

#define INF 1000000000



using namespace std;

ifstream fin("dijkstra.in");

ofstream fout("dijkstra.out");



struct arc{

    int nod, cost;

};



vector <arc> G[MAX];

priority_queue <arc> pq;



int n, m;

int x, y, c;

int cmin[MAX];

bool uz[MAX];



void citire();

void dijkstra();

void afisare();



inline bool operator<(arc x, arc y)

{

    return x.cost > y.cost;

}



int main()

{

    citire();

    dijkstra();

    afisare();

    return 0;

}



void citire()

{int i;

arc aux;



    fin >> n >> m;

    for(i=1;i<=m;i++)

    {

        fin >> x >> y >> c;



        aux.nod = y;

        aux.cost = c;

        G[x].push_back(aux);

    }

}



void dijkstra()

{arc vecin, varf;

int i, cost, nod;

    for(i=1;i<=n;i++)

        cmin[i] = INF;



    cmin[1] = 0;

    uz[1] = true;



    pq.push({1, 0});



    while(!pq.empty())

    {

        varf = pq.top();

        pq.pop();



        nod = varf.nod;

        cost = varf.cost;



        if(cost > cmin[nod])

            continue;



        for(i=0;i<G[nod].size();i++)

        {

            vecin = G[nod][i];



            if(cost + vecin.cost < cmin[vecin.nod])

            {

                cmin[vecin.nod] = cost + vecin.cost;

                pq.push({vecin.nod, cost + vecin.cost});

            }

        }

    }

}



void afisare()

{int i;



    for(i=2;i<=n;i++)

        if(cmin[i] == INF) fout << 0 << ' ';

        else fout << cmin[i] << ' ';

}