#include <iostream>
#include <fstream>
#include <bitset>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int N = 50001, oo = 2e9;

int n;
vector <pair<int, int>> L[N];
set<pair<int, int> > s; // first = distanta pana la nod, second = nod
vector <int> dist;

void Read()
{
    int m;
    ifstream fin("fisier.in");
    fin >> n >> m;
    dist.resize(n + 1, oo);
    while (m--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        L[x].push_back({y, cost});
    }
    fin.close();
}

void Dijkstra()
{
    dist[1] = 0;
    s.insert({0, 1});
    while (!s.empty())
    {
        pair<int, int> curr = *s.begin();
        s.erase(s.begin());
        for (auto &next : L[curr.second]) // curr.second = nodul curent, next = adiacent(next.first = nod, next.second = costul muchiei)
            //curr.first = distanta pana la nodul curent
            if (dist[next.first] > curr.first + next.second)
            {
                if (dist[next.first] != oo)
                    s.erase(s.find({dist[next.first], next.first})); // daca distanta e diferita de infinit => nodul este deja in set
                    //caut pozitia la care e in set si o sterg
                s.insert({curr.first + next.second, next.first});
                dist[next.first] = curr.first + next.second;
            }
    }
}

void Write()
{
    ofstream fout ("fisier.out");
    for(int i = 2; i <= n; i++)
        (dist[i] == oo) ? fout << "0 " : fout << dist[i] << " ";
    fout.close();
}

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