# include <bits/stdc++.h>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
const int oo = 1e7;
# define x first
# define y second
# define pb push_back
# define mk make_pair
const int nmax = 1e6 + 5;
int d[nmax];
set < pair < int , int > > s;
vector < pair < int , int > > r[nmax];
int main(void)
{
    int n,m,a,b,c;
    fi>>n>>m;
    while (m --)
    {
        fi>>a>>b>>c;
        r[a].pb(mk(b,c));
    }
    for (int i = 1;i <= n;++i) d[i] = oo;
    d[1] = 0;
    s.insert(mk(0,1));
    while (s.size())
    {
        int v = s.begin()->y;
        s.erase(s.begin());
        for (vector < pair < int , int > > :: iterator it = r[v].begin();it != r[v].end();++it)
            if (d[v] + it->y < d[it->x])
            {
                d[it->x] = d[v] + it->y;
                s.insert(mk(d[it->x],it->x));
            }
    }
    for (int i = 2;i <= n;++i) fo << d[i] << ' ';
    return fo << '\n',0;
}