#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

vector < list < pair <int,int> > > L;
set <pair <int,int> > Q;
int tata[60000], d[60000];

void Dijkstra(int s)
{
    Q.insert({0,s});
    while (!Q.empty())
    {
        int current = Q.begin()->second;
        for (auto x: L[current])
        {
            int nod = x.second;
            int cost = x.first;
            if (d[nod] > d[current] + cost)
            {
                if (d[nod] != INT_MAX)
                    Q.erase(Q.find({d[nod],nod}));
                d[nod] = d[current] + cost;
                tata[nod] = current;
                Q.insert({d[nod],nod});
            }
        }
        Q.erase(Q.begin());
    }
}

int main()
{
    int n,m,x,y,z,s = 1;
    fin >> n >> m;
    L.resize(n+1);
    for (int i = 0 ; i < m ; i++)
    {
        fin >> x >> y >> z;
        L[x].push_back({z,y});
    }
        for (int i = 0 ; i <= n; i++)
    {
        d[i] = INT_MAX;
        tata[i] = 0;
    }
    d[s] = 0;
    Dijkstra(s);
    for (int i = 2; i <= n; i++)
        if (tata[i] != 0)
            fout << d[i] << " ";
        else fout << 0 << " ";
    fin.close();
    fout.close();
    return 0;
}