#include <fstream>
#include <queue>
#include <vector>
#define inf 1 << 30
using namespace std;

struct vecin
{
    int dest;
    int dist;

    vecin(int dest = 0, int dist = 0): dest(dest), dist(dist)
    {

    }
};

int n, m;
vector<vecin> graf[50010];
int d[50010];

struct cmp
{
    bool operator()(int x, int y)
    {
        return d[x] > d[y];
    }
};
priority_queue<int, vector<int>, cmp> coada;

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

void citire()
{
    fin >> n >> m;
    int x, y, t;

    for (int i = 0; i < m; i++)
    {
        fin >> x >> y >> t;
        graf[x].push_back(vecin(y, t));
    }

    for (int i = 1; i <= n; i++)
        d[i] = inf;
}

void dijkstra()
{
    coada.push(1);
    d[1] = 0;
    int p, v, t;
    while (!coada.empty())
    {
        p = coada.top();
        coada.pop();

        for (int i = 0; i < graf[p].size(); i++)
        {
            v = graf[p][i].dest;

            t = d[p] + graf[p][i].dist;
            if (t < d[v])
            {
                d[v] = t;
                coada.push(v);
            }
        }
    }
}

void rezolvare()
{
    dijkstra();
}

void afisare()
{
    for (int i = 2; i <= n; i++)
        if (d[i] != inf)
            fout << d[i] << ' ';
        else
            fout << "0 ";
    fout << '\n';
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}