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

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

set <int> q;
set <int> :: iterator it;

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

void dfs(int node, int dc)
{
    cm[node] = 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 < cm[i.first])
                cn = 1;
        }
    }
    v[node] = 0;
}

void bellman_ford (int node)
{
    int t;
    q.insert(node);
    cm[node] = 0;
    while(!q.empty())
    {
        it = q.begin();
        t = *it;
        q.erase(q.begin());
        for(auto i:gr[t])
        {
            if(cm[i.first] > cm[t] + i.second)
            {
                cm[i.first] = cm[t] + i.second;
                q.insert(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;
}