#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define NM 50002
#define INF 250000000
using namespace std;

vector <pair <int, int>> gr[NM];

queue <int> q;

bitset <NM> qq;

int n, m, a, b, c, v[NM], cm[NM];

void bellman_ford (int node)
{
    int t;
    q.push(node);
    qq[node] = 1;
    cm[node] = 0;
    while(!q.empty())
    {
        t = q.front();
        qq[t] = 0;
        q.pop();
        for(auto i:gr[t])
        {
            if(cm[i.first] > cm[t] + i.second)
            {
                cm[i.first] = cm[t] + i.second;
                if(qq[i.first] == 0)
                {
                    q.push(i.first);
                    qq[i.first] = 1;
                }

            }
        }
    }
}

int main()
{
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        gr[a].push_back(make_pair(b, c));
    }
    for(int i = 1; i <= n; i++)
        cm[i] = INF;
    bellman_ford(1);
    for(int i = 2; i <= n; i++)
        fout << cm[i] << " ";
    return 0;
}