#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct node{
    int val;
    int cost;
};

struct heapnode{
    int val;
    long long dist;
    bool operator < (const heapnode &other) const{
        return dist>other.dist;
    }
};

const int nmax=5e4, mmax=25e4;
const long long distmax=mmax*2e5;
int n, m;
vector<node> G[nmax+1];
priority_queue<heapnode> heap;
long long dist[nmax+1];

int main()
{
    fin >> n >> m;
    int a, b, c;
    for(int i=0; i<m; i++)
    {
        fin >> a >> b >> c;
        G[a].push_back({b,c});
    }
    for(int i=2; i<=n; i++)
        dist[i]=distmax;
    heap.push({1,0});
    heapnode t;
    while(!heap.empty())
    {
        t = heap.top();
        heap.pop();
        for(node x: G[t.val])
            if(dist[x.val] > dist[t.val] + x.cost)
            {
                dist[x.val]=dist[t.val] + x.cost;
                heap.push({x.val, dist[x.val]});
            }
    }
    for(int i=2; i<=n; i++)
        fout << dist[i] << ' ';
    return 0;
}