#include <fstream>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

ifstream fin ("dmin.in");
ofstream fout ("dmin.out");

int n, m, C[1510], S[1510];
vector < pair < int, double > > V[1510];
set < pair < double, int > > H;

int main()
{
    fin >> n >> m;
    for (int x, y, c, i = 1; i <= m; i ++)
    {
        fin >> x >> y >> c;
        double cost = log2(c);
        V[x].push_back( { y, cost } );
        V[y].push_back( { x, cost } );
    }

    memset (C, 127, sizeof(C));
    C[1] = 1;
    S[1] = 1;
    H.insert( { 0, 1 } );
    while (!H.empty())
    {
        pair < double, int > best = *H.begin();
        H.erase(best);

        for (vector < pair < int, double > > :: iterator it = V[best.second].begin(); it != V[best.second].end(); it ++)
        {
            if (best.first + it->second == C[it->first])
            {
                S[it->first] += S[best.second];
                if (S[it->first] >= 104659) S[it->first] -= 104659;
            }
            else if (best.first + it->second < C[it->first])
            {
                C[it->first] = best.first + it->second;
                H.insert( { C[it->first], it->first } );

                S[it->first] = S[best.second];
            }
        }
    }

    for (int i = 2; i <= n; i ++) fout << S[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}