#include <queue>
#include <fstream>
#include <vector>
using namespace std;
#define x first
#define dist second
#define nod pair<int,int>
const int NMAX=50001,Inf=NMAX*1000;
int n,m,d[NMAX];
// Se da un graf cu N noduri si M arce
//a se determine lungimea minima a drumului de la nodul 1 la fiecare din nodurile 2, 3, ..., N-1, N
// si sa se afiseze aceste lungimi.


// Lungimea unui drum este data de suma lungimilor arcelor care constituie drumul.
// graf orientat ponderat
// a e vector de nod, unde nod e pair [int][int]
vector< nod > a[NMAX];
struct cmp{
    bool operator()(const int A,const int B){
        return d[A]>d[B];
    }
};

priority_queue< int, vector<int> ,cmp > pq;
bool u[NMAX];
void read(){
//    citire
    int i,j,k;
    ifstream f("dijkstra.in");
    f>>n>>m;
    while (m--){
        f>>i>>j>>k;
//        lista de vecini
        a[i].push_back(make_pair(j,k));
    }
}
void dijkstra(){
    int k;
    vector<nod>::iterator it;
//    marchez toate nodurile ca fiind nevizitate
    for (k=1;k<=n;++k)
        d[k]=Inf,u[k]=false;
//    adaug in coada de prioritati (implementata ca un heap ) primul nod
    pq.push(1);
    d[1]=0;u[1]=true;
//    in while scot nodul cu prioritate minima si ii adauga toti vecinii cu noile distante
    while (!pq.empty()){
        k=pq.top();
        pq.pop();
        u[k]=false;
//        iau toti vecinii nodului k, iar daca distanta d[k] + it -> dist < decat vechia distanta([it]->x)
//  actualizez si adaug din nou
        for (it=a[k].begin();it!=a[k].end();++it)
            if (d[it->x]>d[k]+it->dist){
                d[it->x]=d[k]+it->dist;
                if (!u[it->x]) pq.push(it->x),u[it->x]=true;
            }
    }
}
void write(){
    ofstream g("dijkstra.out");
    for (int i=2;i<=n;++i){
        if (d[i]==Inf) d[i]=0;
        g<<d[i]<<' ';
    }
}
int main(){
    read();
    dijkstra();
    write();
    return 0;
}