#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define fastIO ios_base::sync_with_stdio(NULL);cin.tie(NULL);
#define testCases int tc;cin>>tc;while(tc--);
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(),(a).end()
#define PI 3.1415926535897932384626433832795l
template<typename T> inline T gcd(T a,T b){return (b?__gcd(a,b):a);}
template<typename T> inline T lcm(T a,T b){return (a*(b/gcd(a,b)));}
const int NMAX = 5 * 1e5 + 5;
const int oo = 1e9;
static inline void read();
static inline void dijkstra();
static inline void print();
static inline void solve();
std::vector<pair<int,int>> g[NMAX];
int n, m, d[NMAX];
bool use[NMAX];

int main(int argc, char** argv)
{

    (void)! freopen ("dijkstra.in", "r", stdin);
    (void)! freopen ("dijkstra.out", "w", stdout);
    fastIO

    // testCases
    solve();

    return 0;
}

static inline void solve()
{
    read();
    dijkstra();
    print();
}

static inline void read()
{
    cin >> n >> m;
    int x, y, c;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> x >> y >> c;
        g[x].push_back({y, c});
    } 
}

static inline void print()
{
    for (int i = 2; i <= n; ++ i)
    {
        if(d[i] == oo) d[i] = 0;
        cout << d[i] << ' ';
    } 
    cout << '\n';
}

static inline void dijkstra()
{
    for (int i = 2; i <= n; ++ i) d[i] = oo;
    for (int i = 1; i <= n; ++ i)
    {
        int min = oo, nod;
        for (int i = 1; i <= n; ++ i)
            if (d[i] < min && use[i] == 0)
                min = d[i], nod = i;
        use[nod] = 1;
        for (int i = 0; i < (int)g[nod].size(); ++ i)
        {
            int vecin = g[nod][i].first;
            int cost = g[nod][i].second;
            d[vecin] = std::min(d[vecin], d[nod] + cost);
        }
    } 
}