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

#define INF (1 << 29)

using namespace std;

struct arista{ int nodo, costo, cuadra; };

struct grafo{
    vector < vector <arista> > adj;
    vector < int > aRec;
    int nodos, aristas;

    void leer(istream &in){
        in >> nodos >> aristas;

        adj.resize(nodos + 1);
        aRec.resize(aristas + 1);

        for(int i = 1; i <= aristas; i++){
            int d, h, k;

            in >> d >> h >> k;

            adj[d].push_back({h, k, i});
        }
    }

    void DPCaminos(const int &nodo, vector <int> &cRc, const vector < vector < arista > > &subAdj, const int &arSec){
        for(int i = 0; i < int(subAdj[nodo].size()); i++){
            DPCaminos(subAdj[nodo][i].nodo, cRc, subAdj, subAdj[nodo][i].cuadra);

            if(arSec != (-1))
                aRec[arSec] += (subAdj[nodo][i].cuadra);
        }

        if((arSec != -1) && !int(subAdj[nodo].size())) aRec[arSec] += 1;
    }

    void dijkstra(const int &inicial){
        vector <int> d((nodos + 1), INF), cRc((nodos + 1), 1);
        vector <arista> p(nodos + 1);
        vector < vector < arista > > subAdj(nodos + 1);

        d[inicial] = 0;
        p[inicial] = {0, 0, 0};
        p[0] = {-1, -1, -1};

        priority_queue < pair <int, int> > pq;

        pq.push({0, inicial});

        while(int(pq.size())){
            int nodo = pq.top().second;
            int dist = (pq.top().first * (-1));

            pq.pop();

            for(int i = 0; i < int(adj[nodo].size()); i++){
                int nV = adj[nodo][i].nodo;
                int cV = adj[nodo][i].costo;
                int caV = adj[nodo][i].cuadra;

                if((dist + cV) < d[nV]){
                    d[nV] = (dist + cV);

                    p[nV] = {nodo, cV, caV};

                    pq.push({(d[nV] * (-1)), nV});
                }
            }
        }

        for(int i = 1; i <= nodos; i++)
            if(i != inicial)
                subAdj[p[i].nodo].push_back({i, p[i].costo, p[i].cuadra});

        DPCaminos(inicial, cRc, subAdj, (-1));

        /************************BORRAR*************************/
        /**********/for(int i = 1; i <= aristas; i++)/**********/
        /**********/    cout << aRec[i] << " ";      /**********/
        /**********/cout << "\n";                    /**********/
        /************************BORRAR*************************/
    }

    void resolver(istream &in, ostream &out){
        leer(in);

        for(int i = 1; i <= nodos; i++)
            dijkstra(i);
    }
};

int main()
{
    ifstream in("congestion.in", fstream::in);
    ofstream out("congestion.out", fstream::out);

    grafo g;

    g.resolver(in, cout);

    in.close();
    out.close();

    return 0;
}