#include <queue>
#include <cstdio>
#include <vector>
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 comp
{
    public:
        bool operator() ( const edge &a,const edge &b) const
        {
            return a.cost <= b.cost;
        }
};

priority_queue <edge,vector<edge>,comp> q;
vector<edge> graf[maxn];


void dijkstra()
{
    edge cr;
    int i;
    while(!q.empty())
    {
        cr = q.top();
        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;
}