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

///Complexitate O ( m * log n )

int n, m;
/// n - cate noduri sunat
/// m - cate legaturi sunt

int drum[50007];
/// drum[i] - lungimea minima

bool viz[50007];
/// viz[i] = 0 nevizitat
/// viz[i] = 1 vizitat

vector <pair <int, int> > L[50007];
/// L[i] - legaturile cu alte noduri
/// L[i].first - nodul de care este legat i
/// L[i].second - costul

priority_queue <pair <int, int> > q;
/// prima valoare din coada retine drumul
/// a doua valoare din coada este nodul

void Dijkstra()
{
    int el, i, nod, cost;
    drum[1]=0;
    q.push({0, 1}); ///initializam coada

    while (!q.empty())
    {
        el=q.top().second; /// el=nodul curent
        q.pop();

        if (!viz[el])
        {
            viz[el]=1;
            for (i=0; i<L[el].size(); i++)
            {
                nod=L[el][i].first;
                cost=L[el][i].second;
                if (drum[nod]>drum[el]+cost)
                /// actualizam minimul daca este cazul
                {
                    drum[nod]=drum[el]+cost;
                    q.push({-drum[nod], nod});
                    /// distanta minima sa fie prima
                }
            }
        }
    }

    ofstream fout ("dijkstra.out");
    for (i=2; i<=n; i++)
        fout << drum[i] << " ";
    fout << "\n";
    fout.close();
}

int main()
{
    int i, x, y, z;

    ifstream fin ("dijkstra.in");

    fin >> n >> m;

    for (i=1; i<=m; i++)
    {
        fin >> x >> y >> z;
        L[x].push_back({y, z});
    }

    fin.close();

    for (i=1; i<=n; i++)
        drum[i]=LMax;

    Dijkstra();

    return 0;
}