#include <fstream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX;

struct node{
    int nod;
    int val;
    bool operator <(const node &other)const{
        return val < other.val;
    }
};

struct edge{
    int nod;
    int cost;
};


ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
priority_queue <node> pq;
vector <vector<edge>> graph;
vector <int> dist;

void djik(int start){
    pq.push({start, 0});
    dist[start] = 0;
    while(!pq.empty()){
        node crt = pq.top();
        pq.pop();
        if(dist[crt.nod] < crt.val)
            continue;
        for(auto vecin : graph[crt.nod]){
            int distnou = dist[crt.nod] + vecin.cost;
            if(distnou < dist[vecin.nod]){
                dist[vecin.nod] = distnou;
                pq.push({vecin.nod, distnou});
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    for(int i = 0; i < m; i++){
        edge crt;
        int a;
        cin >> a >> crt.nod >> crt.cost;
        graph[a].push_back(crt);
    }
    dist.assign(n + 1, INF);
    djik(1);
    for(int i = 2; i <= n; i++){
        cout << dist[i] << ' ';
    }
    return 0;
}