#include <bits/stdc++.h>
using namespace std;
int INF = 1e9;
int n, m;
struct Edge {
  int to, cost;
  Edge(int to, int cost) : to(to), cost(cost) {}
};
vector<Edge> g[105];
vector<vector<long long> > d(105, vector<long long>(105));
vector<vector<pair<long long, int> > > costvec(
    105, vector<pair<long long, int> >(105));
vector<bool> use(1005, false);
void warshall_floyd(void) {
  for (int k = 0; k < (n); k++)
    for (int i = 0; i < (n); i++)
      for (int j = 0; j < (n); j++) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
}
int main(void) {
  cin >> n >> m;
  for (int i = 0; i < (105); i++)
    for (int j = 0; j < (105); j++) d[i][j] = INF;
  for (int i = 0; i < (105); i++) d[i][i] = 0;
  for (int i = 0; i < (n); i++)
    for (int j = 0; j < (n); j++) costvec[i][j] = make_pair(INF, INF);
  for (int i = 0; i < (m); i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    g[a].push_back(Edge(b, c));
    g[b].push_back(Edge(a, c));
    d[a][b] = c;
    d[b][a] = c;
    costvec[a][b] = make_pair(c, i);
    costvec[b][a] = make_pair(c, i);
  }
  warshall_floyd();
  int ans = m;
  int now = 0;
  for (int i = 0; i < (n); i++) {
    for (int j = 0; j < (n); j++) {
      cout << d[i][j] << " ";
    }
    cout << endl;
  }
  for (int k = 0; k < (n); k++) {
    for (int i = 0; i < (n); i++)
      for (int j = 0; j < (n); j++) {
        if (d[k][i] == d[k][j] + costvec[i][j].first &&
            use[costvec[i][j].second] == false) {
          cout << i << j << k << endl;
          now++;
          use[costvec[i][j].second] = true;
        }
      }
  }
  cout << m - now << endl;
  return 0;
}
