#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <set>
#define nl '\n'

using namespace std;

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

const int NMAX = 5e4+5;
const long long int INF = 1e18;

int n, m;
long long int dist[NMAX];
struct pereche
{
    long long int d;
    int nod;
};

struct fun
{
    bool operator()(const pereche& a, const pereche& b) const
    {
        if (a.d == b.d)
            return a.nod < b.nod;
        return a.d < b.d;
    }
};

vector<pereche> adj[NMAX];
set<pereche, fun> q;
pereche aux;

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back({w, v});
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    q.insert({0, 1});
    while (!q.empty())
    {
        aux = *q.begin();
        q.erase(q.begin());
        int i = aux.nod;
        for (pereche j : adj[i])
        {
            if (aux.d+j.d < dist[j.nod])
            {
                auto it = q.find({dist[j.nod], j.nod});
                if (it != q.end())
                    q.erase(it);
                dist[j.nod] = aux.d+j.d;
                q.insert({dist[j.nod], j.nod});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
    return 0;
}