#include <bits/stdc++.h>
using namespace std;

int const oo = 1000000000;
int const Nmax = 50005;

struct Nod
{
    int nod, cost;
    bool operator < (const Nod &e) const
    {
        return cost > e.cost;
    }
};

int n, m;
bool viz[Nmax];
int d[Nmax];

vector < Nod >L[Nmax];
priority_queue < Nod > q;

void Read()
{
    ifstream fin("dijkstra.in");
    fin >> n >> m;
    int i, x, y, cost;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        L[x].push_back({y, cost});
    }
    fin.close();
}

inline void Init()
{
    for (int i = 1; i <= n; i++)
        d[i] = oo;
}

void Dijakstra()
{
    int vecin, cost, nod;

    d[1] = 0;
    q.push({1, 0});

    while(!q.empty())
    {
        nod = q.top().nod;
        q.pop();
        if (!viz[nod])
        {
            viz[nod] = true;
            for (auto i : L[nod])
            {
                vecin = i.nod;
                cost = i.cost;

                if (d[vecin] > d[nod] + cost)
                {
                    d[vecin] = d[nod] + cost;
                    q.push({vecin, d[vecin]});
                }
            }
        }

    }
}

void Afisare()
{
    ofstream fout ("dijkstra.out");
    int i;
    for (i = 2; i <= n; i++)
        if (d[i] != oo)
                fout << d[i] << " ";
        else    fout << "0 " << " ";
    fout << "\n";
    fout.close();
}

int main()
{
    Read();
    Init();
    Dijakstra();
    Afisare();
    return 0;
}