#include <bits/stdc++.h>

using namespace std;

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

int n, m;
struct elem
{
    int nod, cost;
    bool operator < (const elem other) const
    {
        return cost > other.cost;
    }
};

vector<elem> v[50505];
int ans[50505];
priority_queue<elem> coada;

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        ans[i] = 2e9;
    }
    while(m--)
    {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back({b,c});
    }
    coada.push({1,0});
    /// costul minim cu care a ajuns in nod
    while(!coada.empty())
    {
        int nod = coada.top().nod;
        int cost = coada.top().cost;
        coada.pop();
        if(ans[nod] != 2e9)
            continue;
        ans[nod] = cost;
        for(auto it : v[nod])
        {
            if(ans[it.nod] == 2e9)
            {
                coada.push({it.nod, cost + it.cost});
            }
        }
    }
    for(int i = 2 i <= n; i ++)
    {
        if(ans[i] == 2e9)
        {
            fout << 0 << ' ';
        }
        else
        {
            fout << ans[i] << ' ';
        }
    }
    fout << '\n';
    return 0;
}