#include <bits/stdc++.h>
using namespace std;
 
#define N 50001
#define fi first
#define se second
#define MOD 1000000007
 
#define pb push_back
 
#define ll long long
 
#define eps 1.0e-9
#define inf 1e9 + 5
#define double long double
 
#define pp pair<int,int>

vector< pp > adj[N];
int dis[N],dp[N];

int main()
{
  ios::sync_with_stdio(0);
  int i,j,k,m,n,t;
  cin>>n>>m;
  for(i=0;i<m;i++)
  {
    int u,v,w;
    cin>>u>>v>>w;
    //u--;v--;
    adj[u].pb({w,v});
    adj[v].pb({w,v});
  }
  priority_queue< pp , vector<pp > , greater<pp> > pq;
  for(int i=0;i<=n;i++) dis[i] = INT_MAX;
  dis[1] = 0;
  dp[1] = 1;
  pq.push({0,1});

  while(!pq.empty())
  {
    pp tp = pq.top();
    int u = tp.se;
    int d = tp.fi;
    pq.pop();
    if(dis[u]<d) continue;

    for(i=0;i<adj[u].size();i++)
    {
      int v = adj[u][i].se;
      int w = adj[u][i].fi;
      if(d + w <= dis[v] )
      {
        //dp[v] += dp[u];
		if(dis[v]==d+w) dp[v] += dp[u];
        if(d + w < dis[v])
        {
          dis[v] = d + w;
          dp[v] = dp[u];
          pq.push({dis[v],v}); 
        }
      }
    }
  }
  
  cout<<endl;

  for(int i = 1;i<=n;i++)
  {
    cout<<i<<" dis = "<<dis[i]<<" ways = "<<dp[i]<<endl;
  }





}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBOIDUwMDAxCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwogCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiAKI2RlZmluZSBsbCBsb25nIGxvbmcKIAojZGVmaW5lIGVwcyAxLjBlLTkKI2RlZmluZSBpbmYgMWU5ICsgNQojZGVmaW5lIGRvdWJsZSBsb25nIGRvdWJsZQogCiNkZWZpbmUgcHAgcGFpcjxpbnQsaW50PgoKdmVjdG9yPCBwcCA+IGFkaltOXTsKaW50IGRpc1tOXSxkcFtOXTsKCmludCBtYWluKCkKewogIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogIGludCBpLGosayxtLG4sdDsKICBjaW4+Pm4+Pm07CiAgZm9yKGk9MDtpPG07aSsrKQogIHsKICAgIGludCB1LHYsdzsKICAgIGNpbj4+dT4+dj4+dzsKICAgIC8vdS0tO3YtLTsKICAgIGFkalt1XS5wYih7dyx2fSk7CiAgICBhZGpbdl0ucGIoe3csdn0pOwogIH0KICBwcmlvcml0eV9xdWV1ZTwgcHAgLCB2ZWN0b3I8cHAgPiAsIGdyZWF0ZXI8cHA+ID4gcHE7CiAgZm9yKGludCBpPTA7aTw9bjtpKyspIGRpc1tpXSA9IElOVF9NQVg7CiAgZGlzWzFdID0gMDsKICBkcFsxXSA9IDE7CiAgcHEucHVzaCh7MCwxfSk7CgogIHdoaWxlKCFwcS5lbXB0eSgpKQogIHsKICAgIHBwIHRwID0gcHEudG9wKCk7CiAgICBpbnQgdSA9IHRwLnNlOwogICAgaW50IGQgPSB0cC5maTsKICAgIHBxLnBvcCgpOwogICAgaWYoZGlzW3VdPGQpIGNvbnRpbnVlOwoKICAgIGZvcihpPTA7aTxhZGpbdV0uc2l6ZSgpO2krKykKICAgIHsKICAgICAgaW50IHYgPSBhZGpbdV1baV0uc2U7CiAgICAgIGludCB3ID0gYWRqW3VdW2ldLmZpOwogICAgICBpZihkICsgdyA8PSBkaXNbdl0gKQogICAgICB7CiAgICAgICAgLy9kcFt2XSArPSBkcFt1XTsKCQlpZihkaXNbdl09PWQrdykgZHBbdl0gKz0gZHBbdV07CiAgICAgICAgaWYoZCArIHcgPCBkaXNbdl0pCiAgICAgICAgewogICAgICAgICAgZGlzW3ZdID0gZCArIHc7CiAgICAgICAgICBkcFt2XSA9IGRwW3VdOwogICAgICAgICAgcHEucHVzaCh7ZGlzW3ZdLHZ9KTsgCiAgICAgICAgfQogICAgICB9CiAgICB9CiAgfQogIAogIGNvdXQ8PGVuZGw7CgogIGZvcihpbnQgaSA9IDE7aTw9bjtpKyspCiAgewogICAgY291dDw8aTw8IiBkaXMgPSAiPDxkaXNbaV08PCIgd2F5cyA9ICI8PGRwW2ldPDxlbmRsOwogIH0KCgoKCgp9

MyAzCjEgMiAxCjEgMyAzCjIgMyAx

3 3
1 2 1
1 3 3
2 3 1