#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define inf 2000000000

using namespace std;

int n,m;

const int NMAX = 50005;
struct lista{
int v,cost; /// v este partea a doua a muchei si cost este costul acesteia
};

vector<lista>L[NMAX];
bool viz[NMAX];
int sol[NMAX];

struct coada{
int nod,cost; /// nod este nodul curent, iar cost este costul de pana aici de la nodul original

    bool operator < (const coada &x) const{
        return cost > x.cost;
    }

};

priority_queue<coada>pq;

void bfs(int nod) /// bfs cu dijkstra
{
    for(int i = 1 ; i <= n ; i ++)
        sol[i] = inf;
    coada temp;
    temp.nod = nod;
    temp.cost = 0;
    pq.push(temp);
    while(!pq.empty())
    {
        temp = pq.top();
        int val = temp.nod;
        int cst = temp.cost;

        pq.pop();
        if(sol[val] != inf)
            continue;

        sol[temp.nod] = cst;

        for(vector<lista>::iterator it = L[val].begin() ; it != L[val].end() ; it++)
        {

            lista temp1 = *it; /// aici punem valoare din iterator in temp1
            coada aux;
            aux.nod = temp1.v;
            aux.cost = temp1.cost + cst;
            pq.push(aux);
        }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int u , v, c;
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= m ; i++)
    {
        scanf("%d%d%d",&u,&v,&c);
        lista temp;
        temp.cost = c;
        temp.v = v;
        L[u].push_back(temp);
    }
    bfs(1);
    for(int i = 2 ; i <= n ; i++)
        printf("%d ",sol[i]);
    return 0;
}