#include <cstdio>
#include <fstream>
#include <queue>
#define inff 0x3f3f3f
#define MAX_N 50001

using namespace std;

struct nod {int n, cost;};

vector <nod> V[MAX_N];
queue <int> Q;
char viz[MAX_N];
int N,M,D[MAX_N],cati[100];

void citire()
{
    int x,y,z;
    scanf("%d %d",&N,&M);
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d %d %d",&x,&y,&z);
        nod t;
        t.n = y;
        t.cost = z;
        V[x].push_back(t);
    }
}

void solve()
{
    memset(D, inff, sizeof D);

    Q.push(1);
    D[1] = 0;
    cati[1]=1;
    viz[1] ='1';
    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        viz[nod]='0';

        for(typeof V[nod].begin() p = V[nod].begin(); p < V[nod].end(); p++)
            if(D[p->n]>D[nod]+p->cost)
            {
                 cati[p->n]=cati[nod];
                D[p->n]=D[nod]+p->cost;
                if(viz[p->n]!='1')
                {
                    Q.push(p->n);
                    viz[p->n]='1';
                }
            }
            else
               if (D[p->n]==D[nod]+p->cost)
                    cati[p->n]+=cati[nod];
    }
}
void afisare()
{

    for(int i = 2; i <= N; ++i)
      printf("%d ",cati[i]%104659);
    printf("\n");
}

int main()
{
    freopen ("dmin.in","r",stdin);
    freopen ("dmin.out","w",stdout);
    citire();
    solve();
    afisare();
    return 0;
}