#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
ofstream fout("dijkstra.out");
ifstream fin("dijkstra.in");
const int NMAX = 250005;
const int INF = INT_MAX;

typedef struct {
    int nod, cost;
} Varf;

struct cmp {
    bool operator() (Varf a, Varf b) { return a.cost > b.cost; }
};

int n, m;
int viz[NMAX], drum[NMAX];
priority_queue<Varf, vector<Varf>, cmp> q;
vector<Varf> v[NMAX];

void citire()
{
    int a, b, c;
    Varf yolo;

    fin >> n >> m;
    for(int i=1; i<=m; i++) {
        fin >> a >> b >> c;
        yolo.nod = b;
        yolo.cost = c;
        v[a].push_back(yolo);
    }
}

void afis()
{
    for(int i=2; i<=n; i++)
        fout << (drum[i] == INF ? 0 : drum[i]) << ' ';
}

void dijkstra(int first)
{
    for(int i=1; i<=n; i++) drum[i] = INF;
    drum[first] = 0;

    Varf yolo;
    yolo.nod = first;
    yolo.cost = drum[first];
    q.push(yolo);


    while(!q.empty()){
        int aux = q.top().nod;
        q.pop();

        if(viz[aux]) continue;
        viz[aux] = 1;

        while(!v[aux].empty()) {
            yolo = v[aux].back();
            v[aux].pop_back();
            if(drum[aux] + yolo.cost < drum[yolo.nod]){
                drum[yolo.nod] = drum[aux] + yolo.cost;
                yolo.cost = drum[yolo.nod];
                q.push(yolo);
            }
        }
    }

}

int main()
{
    citire();
    dijkstra(1);
    afis();

    fin.close();
    fout.close();
    return 0;
}