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

using namespace std;
int n,m,k;
int x,y,i,c,v,dx;
int d[1501],t[1501];
vector<pair<int,int> >g[1501];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;

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

void dijkstra()
{
    for (i=1;i<=n;i++) d[i]=(1<<30);
    q.push(make_pair(1,1));
    d[1]=1;
    while (q.size()>0)
    {
        x=q.top().second;
        dx=q.top().first;
        for (auto a:g[x])
        {
            v=a.first;
            c=a.second;
            if (d[v]>d[x]*c)
            {
                d[v]=d[x]*c;
                q.push(make_pair(d[v],v));
                t[v]=1;
            }
            else if(d[v]==d[x]*c) t[v]++;
        }
        q.pop();
    }
}

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>dx;
        g[x].push_back(make_pair(y,dx));
        g[y].push_back(make_pair(x,dx));
    }
    dijkstra();
    for (i=1;i<=n;i++) fout<<d[i]<<" ";
    fout<<"\n";
    for (i=1;i<=n;i++) fout<<t[i]<<" ";
}