#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct Vecin
{
    int y, c;

    Vecin(int _y, int _c)
    {
        y = _y, c = _c;
    }

    bool operator > (const Vecin& other) const
    {
        return c > other.c;
    }
};

int n, m, D[50001];
vector<Vecin> G[50001];
bool V[50001];

void Dijkstra(int nod)
{
    for (int i = 2; i <= n; ++i)
        D[i] = 0x3f3f3f3f;

    priority_queue<Vecin, vector<Vecin>, greater<Vecin>> Q;
    Q.emplace(nod, 0);

    while (!Q.empty())
    {
        int x = Q.top().y;
        Q.pop();
        if (V[x] == true)
            continue;
        V[x] = true;
        for (Vecin v : G[x])
        {
            if (!V[v.y] && D[x] + v.c < D[v.y])
            {
                Q.emplace(v.y, D[x] + v.c);
                D[v.y] = D[x] + v.c;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].emplace_back(y, c);
    }
    Dijkstra(1);
    for (int i = 2; i <= n; ++i)
        fout << D[i] << " ";

    return 0;
}