#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
#define GMAX 50010
#define inf 0x3f3f3f3f

#define father(x) (x>>1)
#define left_son(x) (x<<1)
#define right_son(x) ((x<<1) + 1)

struct Heap
{
    int nod;
    int cost;
}heap[GMAX];

int sz = 0;
vector < pair<int,int> > G[GMAX];
int dist[GMAX];
void insert(int nod,int x)
{
    sz++;
    heap[sz].nod = nod;
    heap[sz].cost = x;
    int i = sz;

    while(father(i) >=1 && heap[father(i)].cost > heap[i].cost)
    {
        swap(heap[father(i)].cost,heap[i].cost);
        swap(heap[father(i)].nod,heap[i].nod);
        i=father(i);
    }
}
int getNod()
{
    return heap[1].nod;
}
int getCost()
{
    return heap[1].cost;
}
void pop()
{
    heap[1].nod = heap[sz].nod;
    heap[1].cost = heap[sz].cost;
    sz--;
    int i = 1;
    while(right_son(i) < sz &&
    (heap[right_son(i)].cost < heap[i].cost || heap[left_son(i)].cost < heap[i].cost))
    {
        if(heap[right_son(i)].cost < heap[left_son(i)].cost)
        {
            swap(heap[i].cost,heap[right_son(i)].cost);
            swap(heap[i].nod,heap[right_son(i)].nod);
        }

        else if(heap[right_son(i)].cost > heap[left_son(i)].cost)
        {
             swap(heap[left_son(i)].cost,heap[i].cost);
             swap(heap[left_son(i)].nod,heap[i].nod);
        }


        i=right_son(i);
    }if(left_son(i) < sz && heap[i].cost > heap[left_son(i)].cost)
    {
        swap(heap[i].cost,heap[left_son(i)].cost);
        swap(heap[i].nod,heap[left_son(i)].nod);
    }
}
int main()
{
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        G[x].push_back(make_pair(y,z)); // orientat
    }
    memset(dist,0x3f,sizeof(dist));
    insert(1,0);
    while(sz >= 1)
    {
        int nod = getNod();
        int cost = getCost();
        pop();

        if(dist[nod] != inf && dist[nod] < cost)
            continue;

        dist[nod] = cost;
        //g<<nod<<' '<<cost<<endl;
        for(int i=0;i<G[nod].size();i++)
        {
           insert(G[nod][i].first,cost + G[nod][i].second);
        }
    }

    for(int i=2;i<=n;i++)
    {
        if(dist[i] == inf) g<<-1<<' ';
            else g<<dist[i]<<' ';
    }

    return 0;
}