#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = (1<<31);
const int maxn = 50005;
int cost[maxn];

typedef unsigned short (ushort);

struct edge
{
    ushort nod;
    ushort cost;
};



class heap
{
public:
    edge d[maxn];
    int size;
    heap()
    {
        size = 0;
        memset(&d[0],0,sizeof(d));
    }
    void push(const edge &a)
    {
        d[ ++ size ] = a;
        upheap(size);
    }
    const edge top()
    {
        return d[1];
    }
    edge pop()
    {
        edge ret = d[1];
        swap(d[1],d[size--]);
        down_heap(1);
        return ret;
    }
    void upheap(int nod)
    {
        int tata;
        while(nod > 1)
        {
            tata = nod >> 1;
            if( d[tata].cost > d[nod].cost )
            {
                swap(d[tata],d[nod]);
                nod = tata;
            }
            else
            {
                return ;
            }
        }
    }
    void down_heap(int nod)
    {
        int fiu;
        while( (nod << 1) <= this->size)
        {
            fiu = nod;
            if( d[nod << 1].cost < d[nod].cost )
                fiu = nod << 1;


            if(( nod << 1 ) + 1 <= this->size
               && d[( nod << 1 ) + 1].cost < d[fiu].cost)
                fiu = (nod << 1 ) + 1 ;

            if(fiu != nod)
            {
                swap(d[fiu],d[nod]);
                nod = fiu;
            }
            else
            {
                return ;
            }
        }
    }
    bool empty()
    {
        return !size;
    }
} q;

vector<edge> graf[maxn];


void dijkstra()
{
    edge cr;
    int i;
    while(!q.empty())
    {
        cr = q.pop();
        for( i = graf[ cr.nod ].size() - 1 ; i >= 0 ; -- i )
        {
            if ( cr.cost + graf[cr.nod][i].cost < cost[graf[cr.nod][i].nod] || (!cost[graf[cr.nod][i].nod])  )
            {
                cost[graf[cr.nod][i].nod] = cr.cost + graf[cr.nod][i].cost;
                q.push((edge){graf[cr.nod][i].nod,cost[graf[cr.nod][i].nod]});
            }
        }
    }
}


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,j,n,m;
    int a,b,c;
    scanf("%d %d\n",&n,&m);

    for( i =  1 ; i <= m ; ++ i)
    {
        scanf("%d %d %d\n",&a,&b,&c);
        graf[a].push_back((edge){b,c});
    }
    cost [ 1 ] = 1 ;
    q.push((edge){1,1});
    dijkstra();
    for( i = 2 ; i <= n ; ++ i )
    {
        printf("%d " , cost [ i ] ? cost[i] - 1 : 0 );
    }
    return 0;
}