#include <bits/stdc++.h>

using namespace std;

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

#define limn 50010 /// nr maxim de noduri, deci si numarul maxim de pasi pe care-i putem face
#define infinit 2e9

int n,m;
int path[limn]; /// contor[i] = cel mai scurt drum de la nodul dat (1) pana in nodul i

vector < pair <int,int> > Graf[limn]; ///maxim limn noduri
priority_queue < pair <int,int> > pq;

///Algoritmul Dijkstra din nod in nod
void Dijkstra( int nod_sursa)
{
    int cost,node;
    for(int i=1;i<=n;i++)
        path[i] = infinit; /// le initializam la inceput cu infinit (2e9) cu define ca sa stim daca au fost parcurse
    path[nod_sursa]=0;
    pq.push({0,nod_sursa}); /// punem costul si apoi nodul si {} - pentru pair
    while(!pq.empty()) /// e echivalent cu !prioq.empty()
    {
        node = pq.top().second;
        cost = -pq.top().first;
        pq.pop();
        if(path[node] != infinit && path[node] != 0)
            continue; /// mergem inapoi in while
        path[node] = cost;
        for(auto it:Graf[node]) ///pentru toate elementele din Graf[node]
            if(path[it.first] > cost + it.second )
        pq.push({-(cost+it.second),it.first});
    }
}
int main()
{
    int x,y,c;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>c;
        Graf[x].push_back({y,c}); /// In graf[x] o sa avem y(nodul in care putem merge si c=costul cu care putem merge
    }
    Dijkstra(1); ///Folosim algoritmul Dijkstra din nodul in care incepem( in cazul nostru e 1)
    for(int i=2;i<=n;i++)
            fout<<path[i]<<' ';
    fout.close(); ///inchidem fisierul, nu e obligatoriu
    return 0;
}