#include <stdio.h>
#include <vector>
#include <queue>

#define pb push_back
#define mp make_pair
#define int_max ((1<<31)-1)

using namespace std;

void read();
void dijkstra();
void write();

vector < pair<int, int> > G[50005];
queue <int> coada;
vector <int> d(50005, int_max);

int main()
{
    read();
    dijkstra();
    write();
    return 0;
}

int n, m;
int x, y, z;

void read()
{
    freopen("dijkstra.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for(unsigned int i=1; i <= m ; ++ i)
        scanf("%d %d %d", &x, &y, &z),
        G[x].pb(mp(y, z));
}

void dijkstra()
{
    coada.push(1);
    d[1]=0;
    for(; !coada.empty(); coada.pop())
    {
        int aux=coada.front();
        for(unsigned int i = 0 ; i < G[aux].size() ; ++ i)
        {
            int cost = G[aux][i].second;
            int nod = G[aux][i].first;
            if(d[nod]>d[aux]+cost)
                d[nod]=d[aux]+cost, coada.push(nod);

        }
    }
}
void write()
{
    freopen("dijkstra.out", "w", stdout);
    for(unsigned int i = 2 ;i <= n ; ++ i)
        if(d[i] == int_max)
            printf("0 ");
        else printf("%d " , d[i]);
}