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

vector < pair < int, int > > a[dim];
priority_queue<int, vector< int >, comp> Q;

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 ++)
        dist[j] = oo;
    dist[i] = 0;
    int poz,nod;
    Q.push(i);
    v[i] = true;
    while(!Q.empty())
    {
        poz = Q.top();
        Q.pop();
        v[poz] = false;
        for(int j = 0; j < a[poz].size(); ++ j)
        {
            int nod = a[poz][j].first;
            int cost = a[poz][j].second;
            if(dist[nod] > dist[poz] + cost)
            {
                dist[nod] = dist[poz] + cost;
                if(v[nod] == false)
                {
                    Q.push(nod);
                    v[nod] = true;
                }
            }
        }
    }
}

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