#include<fstream>
#include<list>
#include<queue>
#include<climits>
#include<bitset>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX=50005,INF=INT_MAX;
struct graph{
    int next_node,cost;
};
list<graph>g[NMAX];
int dist[NMAX],n,m;
bitset<NMAX>in_queue;
class cmp{
    bool ok;
    public:
        bool operator()(const int &x, const int &y){
            if(ok)
                return dist[x]<dist[y];
            return dist[x]>dist[y];
        }
};
void read_data(){
    int from,to,cost;
    fin>>n>>m;
    while(m--){
        fin>>from>>to>>cost;
        g[from].push_back({to,cost});
    }
}
void dijkstra(){
    int node;
    fill(dist+2,dist+1+n,INF);
    priority_queue<int,vector<int>,cmp>pq;
    pq.push(1);
    in_queue[1]=true;
    list<graph>::iterator it;
    while(!pq.empty()){
        node=pq.top();
        pq.pop();
        in_queue[node]=false;
        for(it=g[node].begin();it!=g[node].end();++it)
            if(dist[it->next_node]>dist[node]+it->cost){
                dist[it->next_node]=dist[node]+it->cost;
                if(!in_queue[it->next_node]){
                    pq.push(it->next_node);
                    in_queue[it->next_node]=true;
                }
            }
    }
}
void print(){
    int i;
    for(i=2;i<=n;++i){
        if(dist[i]==INF)
            dist[i]=0;
        fout<<dist[i]<<' ';
    }
}
int main(){
    read_data();
    dijkstra();
    print();
}