#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_N 50005
#define inf 0x3f3f3f3f
using namespace std;

struct cmp{
    bool operator()(const pair<int,int> A, const pair<int,int> B)
    {
        return A.second > B.second;
    }
};
vector<pair<int,int> > g[MAX_N];
priority_queue<pair<int,int> , vector<pair<int,int> >, cmp> q;

int dist[MAX_N];
int n,m;

void read()
{
    scanf("%d %d\n",&n, &m);

    int x,y,z;
    for(int i=0; i<m; i++)
    {
        scanf("%d %d %d\n",&x,&y,&z);
        g[x].push_back(make_pair(y,z));
    }
}

void solve()
{
    memset(dist, inf, sizeof(dist));
    dist[1] = 0;
    q.push(make_pair(1,0));
    while(!q.empty())
    {
        pair<int,int> node = q.top();
        q.pop();

        vector< pair<int,int> >::iterator it = g[node.first].begin();
        for(; it != g[node.first].end();it++)
        {
            if( dist[(*it).first] > dist[node.first] + (*it).second)
            {
                dist[(*it).first] = dist[node.first] + (*it).second;
                q.push(make_pair((*it).first,dist[(*it).first]));
            }
        }
    }

    for(int i=2;i<=n;i++,printf(" "))
        if(dist[i] !=inf)
            printf("%d",dist[i]);
        else
            printf("0");
    printf("\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    read();
    solve();

    return 0;
}