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

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

queue <int> q;

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

int dfs(int node, int dc)
{
    v[node] = 1;
    for(auto i:gr[node])
    {
        if(v[i.first] == 0)
        {
            dfs(i.first, dc + i.second);
        }
        else
        {
            if(dc + i.second < 0)
                cn = 1;
        }
    }
    v[node] = 0;
    return dc;
}

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

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;
}