#include <fstream>
#include <vector>

using namespace std;
ifstream fin  ("dijkstra.in");
ofstream fout ("dijkstra.out");

const long int NMAX = 50005;
const int INFINIT = 1 << 30;

struct edge {
    int x, y, z;
};

int N, M, dist[NMAX];
bool vizitat[NMAX];
vector < vector < edge > > lista(NMAX);

void init()
{
    for(int i = 1; i <= N; i++)
        dist[i] = INFINIT;
}

void dijkstra(int nod)
{
    vector < int > coada;
    dist[nod] = 0;
    vizitat[nod] = true;
    for(unsigned int i = 0; i < lista[nod].size(); i++)
    {
        dist[lista[nod][i].y] = lista[nod][i].z;
        coada.push_back(lista[nod][i].y);
    }
    
    while(!coada.empty())
    {
        int mini = 0;
        for(unsigned int i = 1; i < coada.size(); i++)
            if(dist[coada[mini]] > dist[coada[i]])
                mini = i;
        int node = coada[mini];
        vizitat[node] = true;
        coada.erase(coada.begin() + mini);
        
        for(unsigned int i = 0; i < lista[node].size(); i++)
        {
            if(!vizitat[lista[node][i].y])
                coada.push_back(lista[node][i].y);
            if(dist[lista[node][i].y] > dist[lista[node][i].x] + lista[node][i].z)
                dist[lista[node][i].y] = dist[lista[node][i].x] + lista[node][i].z;
        }
    }
    
    for(int i = 1; i <= N; i++)
        if(dist[i] == INFINIT)
            fout << -1 << ' ';
        else
            fout << dist[i] << ' ';
}

int main()
{
    fin >> N >> M; int x, y, z;
    init();
    for(int i = 0 ; i < M; i++)
    {
        fin >> x >> y >> z;
        edge e;
        e.x = x; e.y = y; e.z = z;
        lista[x].push_back(e);
    }
    
    dijkstra(1);
    fin.close();
    fout.close();
    return 0;
}