//m * log(n) < n ^ 2
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMax = 5 * 1e4, oo = 0x3f3f3f3f;

struct Heap{
    int node, dist;
    Heap(int n, int d) : node(n), dist(d){}
    bool operator < (const Heap &other) const{
        return dist > other.dist;
    }
};

priority_queue <Heap> pq;
vector <pair <int, int>> g[NMax + 5];

int n, m;
bool use[NMax + 5];
int dist[NMax + 5];

void Read(){
    fin >> n >> m;
    while (m--){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
    }
}

void Dijkstra(){
    memset(dist, oo, sizeof dist);
    dist[1] = 0;

    pq.emplace(1, 0);
    while (!pq.empty()){
        int node = pq.top().node, distance = pq.top().dist;
        pq.pop();
        if (dist[node] != distance)
            continue;
        for (auto ngh : g[node]){
            if (distance + ngh.second < dist[ngh.first]){
                dist[ngh.first] = distance + ngh.second;
                pq.emplace(ngh.first, dist[ngh.first]);
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (dist[i] == oo)
            dist[i] = 0;
}

void Print(){
    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    fout << '\n';
}

int main(){
    Read();
    Dijkstra();
    Print();
    return 0;
}