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

#define DIM 50005
#define oo (1 << 30)

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,d[DIM];
bool InQueue[DIM]; // InQueue[i] este 1 daca i este in coada de prioritati, sau 0 in caz contrar

struct comparison{
    //structura pt a crea un min-heap
    bool operator() (int x, int y){
        return d[x] > d[y];
    }
};

priority_queue <int, vector <int>, comparison> pq;

struct node{
    int v,c;
    node * next;
}*L[DIM];

void add(int x, int y, int c){
    node *p = new node;
    p->v=y, p->c=c;
    p->next = L[x];
    L[x] = p;
}

void citire(int &n, int &m){
    f>>n>>m;
    int x,y,c;
    //crearea listelor de adiacenta pt fiecare nod
    for(int i=1; i<=m; i++){
        f>>x>>y>>c;
        add(x,y,c);
    }
}

void Dijkstra_Heap(int Start){
    for(int i=1; i<=n; i++)
        d[i] = oo;
    d[Start] = 0;
    pq.push(Start);
    InQueue[Start] = 1;
    while(!pq.empty()){
        int nodCurent = pq.top();
        pq.pop();
        InQueue[nodCurent] = 0;
        for(node * p = L[nodCurent]; p!= NULL; p = p->next)
            if(d[p->v] > d[nodCurent] + p->c){
                d[p->v] = d[nodCurent] + p->c;
                if(InQueue[p->v] == 0){
                    pq.push(p->v);
                    InQueue[p->v] = 1;
                }
            }
    }
}

void afisare(int n, int d[]){
    for(int i=2; i<=n; i++)
        if(d[i] == oo)
            g<<0<<" ";
        else
            g<<d[i]<<" ";
}

int main() {
    citire(n,m);
    Dijkstra_Heap(1);
    afisare(n,d);
}