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

#define INF 2e9

using namespace std;

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

const int MAX_N = 50001;

struct t_muchie{
    int nod;
    int cost;
};

int main()
{
    int n,m;
    fin>>n>>m;

    vector <t_muchie> vecini[MAX_N];
    priority_queue<pair<int,int>> pq;
    bool viz[MAX_N] = {0};
    int costuri[MAX_N];

    costuri[1] = 0;
    for(int i = 2; i <= n; i++)
        costuri[i] = INF;


    for(int i = 1; i <= m; i++){
        int nod1,nod2,cost;
        fin>>nod1>>nod2>>cost;
        t_muchie x = {nod2,cost};
        vecini[nod1].push_back(x);
    }

    pq.push(make_pair(0,1));

    while(!pq.empty()){

        int nod = pq.top().second;
        pq.pop();

        if(!viz[nod]){
            viz[nod]  = true;

            for(int i = 0; i < vecini[nod].size(); i++){

                int vecin = vecini[nod][i].nod;
                int cost = vecini[nod][i].cost;

                if(costuri[vecin] > costuri[nod] + cost){
                    costuri[vecin] = costuri[nod] + cost;
                    pq.push(make_pair(-costuri[vecin],vecin));
                }
            }
        }
    }
    for(int j = 2; j <= n; j++)
    {
        if(costuri[j] == INF)
            fout<<"0 ";
        else
            fout<<costuri[j]<<" ";
    }

    return 0;
}