#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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
{
    coada temp;
    temp.nod = nod;
    temp.cost = 0;
    viz[nod] = true;
    pq.push(temp);
    while(!pq.empty())
    {
        temp = pq.top();
        int val = temp.nod;
        int cst = temp.cost;

        for(vector<lista>::iterator it = L[val].begin() ; it != L[val].end() ; it++)
        {
            lista temp1 = *it; /// aici punem valoare din iterator in temp1
            if(!viz[temp1.v])
            {
                viz[temp1.v] = true;
                coada aux;
                aux.nod = temp1.v;
                aux.cost = temp1.cost + cst;
                pq.push(aux);
            }
        }
        sol[temp.nod] = temp.cost;
        pq.pop();
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n , m , 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;
}