#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int nmax=50005;

vector <pair <int, int> > graph_orientat[nmax];
vector <pair <int, int> > heap;
int valori[nmax];
bool visited[nmax];

bool cmp(pair <int, int> a, pair <int, int> b)
{
    if(a.second==b.second)
        return a.first>b.first;
    return a.second>b.second;
}

void bfs(int start_node)
{
    heap.push_back(make_pair(start_node, 0));
    visited[start_node]=true;
    valori[start_node]=0;
    while(!heap.empty())
    {
        int current_node=heap.back().first;
        heap.pop_back();
        for(int i=0; i<graph_orientat[current_node].size(); i++)
            heap.push_back(make_pair(graph_orientat[current_node][i].first, valori[current_node]+graph_orientat[current_node][i].second));
        sort(heap.begin(), heap.end(), cmp);
        while(visited[heap.back().first]==true)
            heap.pop_back();
        if(heap.size()>0)
        {
            valori[heap.back().first]=heap.back().second;
            visited[heap.back().first]=true;
        }
    }
}

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

    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        graph_orientat[a].push_back(make_pair(b, c));
    }
    for(int i=1;i<=n;i++)
        valori[i]=nmax*20000;
    bfs(1);
    for(int i=2;i<=n;i++)
    {
        if(valori[i]==nmax*20000)
            printf("0 ");
        else
            printf("%d ", valori[i]);
    }
    printf("\n");

    return 0;
}