#include <fstream>
#include <vector>
#include <queue>
#define nmax 50000+5
#define inf 1 << 30
using namespace std;

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

vector<pair<int, int> > graf[nmax];
int pas[nmax];
int n;


struct cmp
{
    bool operator()(const int & a, const int & b)
    {
        return pas[a] > pas[b];
    }
};

priority_queue<int, vector<int>, cmp> heap;

void citire()
{
    int m;
    int x, y, c;

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

void rezolvare()
{
    int curent, vecin;
    int pasT;
    heap.push(1);

    for (int i = 2; i <= n; i++)
        pas[i] = inf;
    while (!heap.empty())
    {
        curent = heap.top();
        heap.pop();

        for (int i = 0; i < graf[curent].size(); i++)
        {
            vecin = graf[curent][i].first;
            pasT = pas[curent] + graf[curent][i].second;

            if (pasT < pas[vecin])
            {
                pas[vecin] = pasT;

                heap.push(vecin);
            }
        }
    }
}

void afisare()
{
    for (int i = 2; i <= n; i++)
        fout << (pas[i] != inf ? pas[i] : 0) << ' ';
    fout << '\n';
}

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