#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
int n,m,A,B,C;
int distante[50001];
bool viz[50001];
vector<pair<int,int>>adiacenta[50001];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>q;
int main()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        f >>A>>B>>C;
        adiacenta[A].push_back({B,C});
    }
    for(int i = 2;i<=n;i++)
    {
        distante[i] = INF;
    }
    /// ideea principala este ca incepem din nodul cu numarul 1 pana la care este distanta 0
    /// si apoi mergem in vecii nodului curent(int acest caz 1) si incercam sa actualizam distanta
    /// in caz ca distanta nou este mai mica decat cea deja trecuta in vector atunci o actualizam
    /// iar in algoritmul mai putin eficient dupa ce treceam prin toti vecinii nodului curent gaseam distanta minima dintre nodurile nevizitate
    /// si incepeam cautarea de acolo, acest lucru mergea deorece toate distantele sunt pozitive iar din moment ce acel nod nevizitat avea distanta minima
    /// dintre toate distantele celorlalte noduri nevizitate nu ar putea deveni si mai mica


    /// dar acest algoritm este mai eficent deoarece gaseste distanta minima la un nod nevizitat cu ajutorul prioriry_queului folosit ca min_heap
    distante[1] = 0;
    q.push({0,1});
    while(!q.empty())
    {
        int curent_nod  = q.top().second;
        int distanta_curenta = q.top().first;
        q.pop();
        if(viz[curent_nod] == 1)
            continue;
        viz[curent_nod] = 1;
        for(auto x:adiacenta[curent_nod])
        {
            int nod_vecin = x.first;
            int cost_drum = x.second;

            if(distante[nod_vecin] > distante[curent_nod] + cost_drum)
            {
                distante[nod_vecin] = distante[curent_nod] + cost_drum;
                q.push({distante[nod_vecin],nod_vecin});
            }
        }
    }
    for(int i = 2 ;i<=n;i++)
        g << distante[i] << ' ';


}