#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct Edge{
    int nod;
    int cost;
};

int main() {
    int noduri, muchii, ind = 0;
    in >> noduri >> muchii;

    vector < int > d(noduri, ind);
    vector < int > viz(noduri, 0);
    vector < vector < Edge > > G(noduri);

    for(int i = 1; i <= muchii; i++)
    {
        int a, b, cost;
        in >> a >> b >> cost;
        out << a << b << cost << "\n";
        Edge edge;
        edge.nod = b;
        edge.cost = cost;

        G[b].push_back(edge);
        for(int i = 1; i<= noduri; i++)
        {

            int minim = ind;
            ind = -1;

            for(int j = 0; j < noduri; j++)
                if(d[j] < minim && viz[j] == 0)
                {
                    minim = d[j];
                    ind = j;
                }
            for(auto edge:G[ind])
                if(d[edge.nod] > d[ind] + edge.cost)
                    d[edge.nod] = d[ind] + edge.cost;
                viz[ind] = 1;
        }
    }
    return 0;
}