#include <fstream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define inf   1000000000
struct edge
{
    int c,dr;
};
queue<int> que;
vector<edge> v[50003];
int d[50003];
bool visited[50003]{false};
 int a,b,c,n,m;
void initialize()
{
    for(int i = 0 ; i <= n ; i++)
        d[i] = inf;
}
void djkstra(int start)
{
    initialize();
    d[start] = 0;
    que.push(start);
    int node;
    int distmin ;
    for(int i = 1 ; i <= n ; i++)
    {
        distmin = inf;
        for(int j = 1 ; j <= n ; j++)
            if ( visited[j] == false && d[j] <= distmin)
            {
                distmin = d[j];
                node = j;
            }

        for(edge e :v[node])
        {
            if( d[node]+e.c < d[e.dr] )
                d[e.dr] = d[node]+e.c;
        }
        visited[node] = true;
    }


}
int main()
{

    in >> n >> m;
    edge e;
    for(int i = 0 ; i < m ; i++)
    {
        in >> a >> e.dr >> e.c;
        v[a].push_back(e);
    }
    djkstra(1);
    for(int i = 2 ; i <= n ; i++)
    {
        out<<((d[i] == inf)?0:d[i])<<" ";
    }


	return 0;
}