#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define infinit (1 << 30)

using namespace std;

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

int n, m, drum[120000];
priority_queue <pair <int, int> > Q;
vector < pair <int, int> > L[100006];


void Read()
{
    fin >> n >> m;
    int x, y, c;
    while(fin >> x >> y >> c)
    {
        L[x].push_back ({y, c});
        //L[y].push_back ({x, c});
    }
}

void Initializare ()
{
    for (int i = 1; i <= n; i++)
        drum[i] = infinit;
}

void Dijkstra ()
{
    int NodDinCareVin, CostMuchieNodDinCareVin, NodIncareMaDuc;
    Q.push ({0, 1});
    drum[1] = 0;
    while (!Q.empty ())
    {
        NodDinCareVin = Q.top().second;
        Q.pop();

        for (int i = 0; i < L[NodDinCareVin].size(); i++)
        {
            NodIncareMaDuc = L[NodDinCareVin][i].first;
            CostMuchieNodDinCareVin = L[NodDinCareVin][i].second;

            if (drum[NodIncareMaDuc] > drum[NodDinCareVin] + CostMuchieNodDinCareVin)
            {
                drum[NodIncareMaDuc] = drum[NodDinCareVin] + CostMuchieNodDinCareVin;
                Q.push ({-drum[NodIncareMaDuc], NodIncareMaDuc});
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (drum[i] != infinit)
            fout << drum[i] << " ";
}

int main()
{
    Read();
    Initializare();
    Dijkstra();
    return 0;
}