#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

const int NMAX = 50005;
const int INF = 0x3f3f3f3f;

vector<pair<int, int>> G[NMAX];

int dist[NMAX];

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

    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int from,to,cost;
        f>>from>>to>>cost;
        G[from].push_back(make_pair(to,cost));
    }

    int dist[NMAX];
    memset(dist,INF,sizeof dist);

    set<pair<int,int>> h;
    h.insert(make_pair(0,1));
    while(!h.empty()){
        int node = h.begin()->second;
        int cost = h.begin()->first;
        h.erase(h.begin());

        for(auto it=G[node].begin();it !=G[node].end();it++){
            int to = it->first;
            int ct = it->second;
            if(dist[to]>ct+cost){
                if(dist[to]!=INF){
                    h.erase(make_pair(dist[to],to));
                }
                dist[to] = ct+cost;
                h.insert(make_pair(dist[to],to));
            }
        }
    }

    for(int i=2;i<=n;i++){
        if(dist[i]==INF)dist[i]=0;
        g<<dist[i]<<" ";
    }
}