#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 w[dim];
struct comp
{
    bool operator()(const int& a, const int& b)
    {
        return (dist[a] > dist[b]);
    }
};
//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;

//queue<int, vector< int > > 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)
//{
//
//}

int main()
{
    int i;
    citire();
    //dij(1);
    for(int j = 1; j <= n; j ++)
        dist[j] = oo;
    dist[1] = 0;
    int poz,nod,cost;
    Q.push(1);
    w[1] = true;
    while(!Q.empty())
    {
        poz = Q.top();
        Q.pop();
        w[poz] = false;
        for(int j = 0; j < a[poz].size(); ++ j)
        {
           nod = a[poz][j].first;
           cost = a[poz][j].second;
            if(dist[nod] > dist[poz] + cost)
            {
                dist[nod] = dist[poz] + cost;
                if(w[nod] == false)
                {
                    Q.push(nod);
                    w[nod] = true;
                }
            }
        }
    }
    for(i = 2; i <= n; i ++)
       if(dist[i] == oo)
        g<<"0 ";
       else
        g<<dist[i]<<" ";
}