#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>
#include <list>
using namespace std;

typedef pair<int, int> oras;
typedef list<oras> vecini;
typedef list<oras>::iterator itn;

const int max_n = 50001;
const int max_m =  250001;
int inf = 1 << 30;

int n, m, dis[max_n], viz[max_n];
priority_queue<oras, vector<oras>, greater<oras> > coada;
vecini vecinii[max_n];

void citeste();
void afiseaza();
void dijkstra();

int main()
{
    citeste();
    afiseaza();
    dijkstra();
    ofstream out("dijkstra.out");
    for( int i = 2; i <= n; i++ )
    {
        if( dis[i] == inf )
            dis[i] = 0;
        out << dis[i] << " ";
    }
    out.close();
    return 0;
}

void dijkstra()
{
    coada.push(make_pair(0,1));
    dis[1] = 0;
    viz[1] = 0;

    while( !coada.empty() )
    {
        int c = coada.top().first;
        int u = coada.top().second;
        coada.pop();
        for( itn i = vecinii[u].begin(); i != vecinii[u].end(); i++ )
        {
            if( dis[i->first] > c + i->second )
            {
               dis[i->first] = c + i->second;
               coada.push( make_pair(dis[i->first], i->first ));
            }
        }
    }
}

void citeste()
{
    int x, y, c;
    ifstream in("dijkstra.in");
    in >> n >> m;
    for( int i = 1; i <= n; i++ )
        dis[i] = inf;
    for( int i = 0; i < m; i++ )
    {
        in >> x >> y >> c;
        vecinii[x].push_back(make_pair(y,c));
        vecinii[y].push_back(make_pair(x,c));
    }
    in.close();
}

void afiseaza()
{
    for( int i = 1; i <= n; i++ )
    {
        cout<< i << "-->";
        for( itn it = vecinii[i].begin(); it  != vecinii[i].end(); it++ )
        {
            cout<< it->first << " cu: " << it->second << " | ";
        }
        cout <<  endl;
    }
}