#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#define MAX 500000000000
//#include <iostream>
using namespace std;
//ifstream cin("jocul.in");
//ofstream cout("jocul.out");
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int x[50003], y[50004];
void dijk(vector<int> nods[], vector<int> cost[], int x[], int y[], int n)
{
    int nod = 0;
    for(int i = 1; i <= n; i++)
        y[i] = 1<<30;
    int v = 0;
    for(int i = 0; i < n; i++)
    {
        int ma = 1<<30, cnod;
        x[nod] = 1;
        for(int j = 0; j < nods[nod].size(); j++)
            if(y[nods[nod][j]] > y[nod] + cost[nod][j] && x[nods[nod][j]] == 0)
                y[nods[nod][j]] = y[nod] + cost[nod][j];
        for(int v = 0; v < n; v++)
            if(y[v] < ma && x[v] == 0){
                ma = y[v];
                cnod = v;
            }
        nod = cnod;
    }
}
int main()
{
    vector<int> nods[50010];
    vector<int> cost[50010];
    int n, m, a, b, c;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        nods[a - 1].push_back(b - 1);
        cost[a - 1].push_back(c);
    }
    dijk(nods, cost, x, y, n);
    for(int i = 1; i < n; i++)
        cout << (y[i] == 1<<30 ? 0 : y[i]) << " ";
    return 0;
}