#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

const int nmax=50005;
const int lim=100000000;

int n, m;

priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > heap;
vector < pair <int, int> > graph[nmax];
int dist[nmax];

void dijkstra(int start_node)
{
    for(int i=1;i<=n;i++)
        dist[i]=lim;
    dist[start_node]=0;
    heap.push(make_pair(0, start_node));
    while(heap.size()>0)
    {
        int nod=heap.top().second;
        int cost=heap.top().first;
        heap.pop();
        if(cost<=dist[nod])
        {
            for(int i=0;i<graph[nod].size();i++)
            {
                int nod_l=graph[nod][i].first;
                int cost_l=graph[nod][i].second;
                if(dist[nod_l]>cost+cost_l)
                {
                    dist[nod_l]=cost+cost_l;
                    heap.push(make_pair(dist[nod_l], nod_l));
                }
            }
        }
    }
}

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

    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        if(dist[i]==lim)
            printf("0 ");
        else
            printf("%d ", dist[i]);
    }
    printf("\n");

    return 0;
}