#include <bits/stdc++.h>
#define optim ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define let auto
#define popcount __builtin_popcount
#define ctzll __builtin_ctzll
#define clzll __builtin_clzll

using namespace std;
string filename = "dijkstra";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");



void getint(int& x) {
    char c;
    while (cin.get(c) && !cin.eof() && isspace(c));
    if (cin.eof()) return;
    x = c - '0';
    while (cin.get(c) && !cin.eof() && isdigit(c)) x = x * 10 + (c - '0');
}


const int sze = 50000;
const int oo = INT_MAX;
int n, m;


vector<pair<int, int>> G[sze + 1];
int D[sze + 1];
bool F[sze + 1];

class compare {
public:
    bool operator()(int a, int b) {
        return D[a] > D[b];
    }
};

void Dijkstra() {
    for (int i = 2; i <= n; ++i) D[i] = oo;
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    while (!q.empty()) {
        auto t = q.top();
        q.pop();
        if(F[t.second]) continue;
        F[t.second] = 1;
        for (auto k : G[t.second]) {
            if (D[k.first] > D[t.second] + k.second) {
                D[k.first] = D[t.second] + k.second;
                q.push({-D[k.first],  k.first});
            }
        }
    }
}

int main() {
    fin >> n >> m;
    int a, b, c;
    while (m--) {
        fin >> a >> b >> c;
        G[a].pb(make_pair( b, c ));
    }
    Dijkstra();
    for (int i = 2; i <= n; ++i) {
        fout << (D[i] == INT_MAX ? 0 : D[i]) << " ";
    }
    


    
    return 0;
}