#include <iostream>
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;

class Muchie {
public:
    int Vec;
    int Cost;
    Muchie () {}
    Muchie (int v, int c) {
        Vec = v;
        Cost = c;
    }
};

class NodData {
public:
    int Nod;
    int MinPath;
    NodData () {}
    NodData (int n, int mp) {
        Nod = n;
        MinPath = mp;
    }
};

bool operator<(const NodData& lhs, const NodData& rhs)
{
    return lhs.MinPath < rhs.MinPath;
}

vector<Muchie> v[50001];
set<NodData> Analyzer;
int Paths[50001];

int main () {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int Noduri, Muchii;
    cin >> Noduri >> Muchii;
    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        cin >> orig >> dest >> cost;
        v[orig].push_back(Muchie(dest, cost));
    }

    Analyzer.insert(NodData(1, 0));
    Paths[1] = 0;
    for (int i = 2; i <= Noduri; i++)
        Paths[i] = 1000000000;

    while (!Analyzer.empty()) {
        int analyze = (Analyzer.begin())->Nod;
        for (int i = 0; i < v[analyze].size(); i++) {
            if (Paths[v[analyze][i].Vec] > Paths[analyze] + v[analyze][i].Cost) {
                Paths[v[analyze][i].Vec] = Paths[analyze] + v[analyze][i].Cost;
                Analyzer.insert(NodData(v[analyze][i].Vec, Paths[v[analyze][i].Vec]));
            }
        }
        Analyzer.erase(Analyzer.begin());
    }

    for (int i = 2; i <= Noduri; i++)
        cout << Paths[i] << " ";
}