#include <fstream>
#include <set>
#include <vector>

#define in "dmin.in"
#define out "dmin.out"
#define LL long long
#define Max_Size 1509
#define Mod 104659
#define oo 100000000000
typedef std :: pair < int, LL> NOD;

std :: ifstream f(in);
std :: ofstream g(out);

int N, M, Count[Max_Size];
LL D[Max_Size];

std :: vector < NOD > V[Max_Size];
std :: set < NOD >    H;

inline void Read_Data() {
    f >> N >> M;

    for(int i = 1, x, y, cost; i <= M; ++i) {
        f >> x >> y >> cost;

        V[x].push_back(std :: make_pair(y, cost));
        V[y].push_back(std :: make_pair(x, cost));
    }
}

void Djikstra() {
    H.insert( {0, 1} );

    while(!H.empty()) {
        NOD nod = *H.begin();
        H.erase( *H.begin() );

        for(auto val : V[nod.second])
            if(D[val.first] > nod.first + val.second && val.first != 1) {
                Count[val.first] = Count[nod.second] % Mod;
                H.erase( {D[val.first], val.first} );

                D[val.first] = nod.first + val.second;
                H.insert( {D[val.first], val.first} );
            }   else if(D[val.first] == nod.first + val.second && val.first != 1)
                        Count[val.first] = (Count[val.first] + Count[nod.second] ) % Mod;

    }
}

int main() {
    Read_Data();

    for(int i = 2; i <= N; ++i) D[i] = oo;
    Count[1] = 1;
    Djikstra();

    for(int i = 2; i <= N; ++i) g << Count[i] << ' ';

    g.close();
    return 0;
}