#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];
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(){
    int i,j,k;
    ifstream f("dijkstra.in");
    f>>n>>m;
    while (m--){
        f>>i>>j>>k;
        a[i].push_back(make_pair(j,k));
    }
}
void dijkstra(){
    int k;
    vector<nod>::iterator it;
    for (k=1;k<=n;++k)
        d[k]=Inf,u[k]=false;
    pq.push(1);
    d[1]=0;u[1]=true;
    while (!pq.empty()){
        k=pq.top();
        pq.pop();
        u[k]=false;
        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;
}