#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)
{
    if (lhs.MinPath == rhs.MinPath)
        return lhs.Nod < rhs.Nod;
    else
        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;
    scanf("%d%d", &Noduri, &Muchii);
    for (int i = 0; i < Muchii; i++) {
        int orig, dest, cost;
        scanf("%d%d%d", &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()) {
        for (set<NodData>::iterator i = Analyzer.begin(); i != Analyzer.end(); i++) {
            //cout << i->Nod << " ";
        }
        //cout << '\n';
        int analyze = (Analyzer.begin())->Nod;
        //cout << "NOD " << analyze << "(" << Paths[analyze] << "):\n";
        Analyzer.erase(Analyzer.begin());
        for (int i = 0; i < v[analyze].size(); i++) {
            int vec = v[analyze][i].Vec;
            //cout << vec << " " << Paths[vec] << " " << v[analyze][i].Cost <<'\n';
            if (Paths[vec] > Paths[analyze] + v[analyze][i].Cost) {
                set<NodData>::iterator it = Analyzer.find(NodData(vec, Paths[vec]));
                if (it!=Analyzer.end()) Analyzer.erase(it);
                Paths[vec] = Paths[analyze] + v[analyze][i].Cost;
                Analyzer.insert(NodData(vec, Paths[vec]));
                //cout << vec << " " << Paths[vec] << '\n';
            }
        }
    }
    //cout << '\n';
    for (int i = 2; i <= Noduri; i++) {
        if (Paths[i] == 1000000000)
            printf("0 ");
        else
            printf("%d ", Paths[i]);
    }
}