#include <stdio.h>
#include <vector>
#include <set>
#define NMax 1000001

using namespace std;

FILE *fin = fopen("dijkstra.in" , "r");
FILE *fout = fopen("dijkstra.out" , "w");

int n , m , d[50005] , nod;

bool cmp(int x , int y)
{
    return (d[x] > d[y]);
}

vector <pair <int , int> > v[50005];
set <int , bool(*)(int , int)> s(cmp);

void dijkstra()
{
    for(int i = 1;  i <= n ; i ++)
        d[i] = NMax;
    d[1] = 0;
    s.insert(1);
    while(!s.empty())
    {
        int p = *s.begin();
        s.erase(p);
        for(int f = 0 ; f < v[p].size() ; f ++)
            if(d[p] + v[p][f].second < d[v[p][f].first])
            {
                s.erase(v[p][f].first);
                d[v[p][f].first] = d[p] + v[p][f].second;
                s.insert(v[p][f].first);
            }
    }
}

int main()
{
    int x , y , cost;
    fscanf(fin , "%d%d" , &n , &m);
    for(int i = 1 ; i <= m ; i ++)
    {
        fscanf(fin , "%d%d%d" , &x , &y , &cost);
        v[x].push_back({y , cost});
    }
    dijkstra();
    for(int i = 2 ; i <= n ; i ++)
        fprintf(fout , "%d " , d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}