#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
#define NMAX 50005
#define inf 1e9
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int, int> > graf[NMAX];
queue<int> coada;

int n,m, distanta[NMAX];
void citire(){
    f>>n>>m;
    for(int i = 0; i < m; i ++)
    {
        int a,b,c;
        f>>a>>b>>c;
        graf[a].push_back({b,c});
    }
}



void dijkstra(){
    for(int i = 2; i <= n; i ++)
        distanta[i] = inf;
    coada.push(1);
    while(!coada.empty()){

        int x = coada.front();
        coada.pop();

        for(int i = 0; i < graf[x].size();  i ++)
        {
            int vecin = graf[x][i].first;
            int cost = graf[x][i].second;
            if(distanta[x] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[x] + cost;
                coada.push(vecin);
            }
        }
    }


}

void afisare(){
for(int i = 2; i <= n; i ++)
    g<<distanta[i]<<" ";

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