#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int MAXN = 50005;
const int INF = 1 << 30;

struct vertex {
    int nod, cost;
}v;

int best[MAXN];//best[i] = costul minim ca sa ajungi de la 1 la i

bool operator<(const vertex& a, const vertex& b) {
  return best[a.nod] > best[b.nod];
}

int N, M, a, it, lung;

int costmin[MAXN];//costmin[i] = costul minim la care se gaseste nodul i in coada
priority_queue<vertex> pq;
bool marked[MAXN];
vector<vertex> G[MAXN];

void read() {
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        fin >> a >> v.nod >> v.cost;
        G[a].push_back(v);
    }
}

void dijkstra() {
    best[1] = 0;
    v.nod = 1;
    v.cost = 0;
    pq.push(v);
    do {
        v = pq.top();
        pq.pop();
        if (marked[v.nod] == false) {
            marked[v.nod] = true;
            lung = G[v.nod].size();
            for (it = 0; it < lung; ++it) {
                if (best[G[v.nod][it].nod] > best[v.nod] + G[v.nod][it].cost) {
                    best[G[v.nod][it].nod] = best[v.nod] + G[v.nod][it].cost;
                    pq.push(G[v.nod][it]);
                }
            }
        }
    }while (!pq.empty());
}

void write() {
    for (int i = 2; i <= N; ++i)
        if (best[i] == INF)
            fout << 0 << ' ';
        else
            fout << best[i] << ' ';
    fout << '\n';
}

int main() {
    read();
    for (int i = 0; i <= N; ++i)
        best[i] = INF;
    dijkstra();
    write();
    fin.close();
    fout.close();
    return 0;
}