#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
#define mod 104659;
#define maxi 999999999999999999
long long x,y,z,n,m,a,c1,b,t[3][250005],nr[50001],k,start[250005],cost[50005],c[500005],viz[50005],cnt[50005],ok=1;
void ford()
{
    int i,ps=1,pi=1,val,k;
    for(i=1;i<=n;i++)
        cost[i]=maxi;
    cost[1]=0;
    c[pi]=1;
    nr[1]=viz[1]=1;
    while(pi<=ps)
    {
        k=c[ps];
        viz[k]=0;
        val=start[k];
        while(val)
        {
            if(cost[k]+t[2][val]<cost[t[0][val]])
            {
                cost[t[0][val]]=cost[k]+t[2][val];
                nr[t[0][val]]=nr[k];
                if(!viz[t[0][val]])
                {
                     viz[t[0][val]]++;
                     c[++pi]=t[0][val];
                }

            }
            else
                if(cost[k]+t[2][val]== cost[t[0][val]])
                    nr[t[0][val]] = (nr[t[0][val]] + nr[k])% mod;
            val = t[1][val];

        }
    }
}
int main()
{
    f>>n>>m;
    f>>x>>y>>z;
    for(int i=1;i<=m;i++)
    {
        k++;
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
        k++;
        t[0][k]=x;
        t[1][k]=start[y];
        start[y]=k;
        t[2][k]=t[2][k-1]=z%mod;
    }
    ford();
    for(int i=2;i<=n;i++)
        g<<nr[i]<<" ";

    return 0;
}