#include<fstream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define oo 100000000
#define pb push_back
#define mp make_pair
#define maxn 50005
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int d[maxn],n,m;
bool v[maxn];
struct comp
{
    bool operator()(const int& a, const int& b)
    {
        return (d[a] > d[b]);
    }
};

vector < pair < int, int > > a[maxn];
priority_queue<int, vector< int >, comp> coada;

inline void citire()
{
    f>>n>>m;
    int i,y,x,c;
    for(i = 1; i<= m; i ++)
    {
        f>>x>>y>>c;
        a[x].pb(mp(y,c));
    }
}

inline void dij(int i)
{
    for(int j = 1; j <= n; j ++)
        d[j] = oo;
    d[i] = 0;
    int p;
    coada.push(i);
    v[i] = true;
    while(!coada.empty())
    {
        p = coada.top();
        coada.pop();
        v[p] = false;
        for(int j = 0; j < a[p].size(); ++ j)
        {
            int nod = a[p][j].first;
            int cost = a[p][j].second;
            if(d[nod] > d[p] + cost)
            {
                d[nod] = d[p] + cost;
                if(v[nod] == false)
                {
                    coada.push(nod);
                    v[nod] = true;
                }
            }
        }
    }
}

int main()
{
    int i;
    citire();
    dij(1);
    for(i = 2; i <= n; i ++)
       if(d[i] == oo)g<<"0 ";
       else g<<d[i]<<" ";
}