After constructing the best data, Max asked Wesley to test the problem.

Wesley submitted the following solution and showed Max that his data were weak (after commenting the code below):

// Dijkstra's shortest path algorithm with vertex 1 as the source
// Function Arguments:
//   adj: an adjacency list representation of a 1-indexed graph, with each edge represented by a pair (to, weight)
// Return Value: a vector containing the shortest distance from vertex 1 for each vertex, or LLONG_MAX if no path exists
vector<long long> dijkstra(const vector<vector<pair<int, long long>>> &adj) {
  vector<long long> d(adj.size(), LLONG_MAX);
  priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
  d[1] = 0;
  pq.emplace(d[1], 1);
  int counter = 0;
  while (!pq.empty()) {
    long long dv = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    // if (dv > d[v]) {
    //   continue;
    // }
    for (auto &&edge : adj[v]) {
      counter++;
      int to = edge.first;
      long long weight = edge.second;
      if (d[to] > d[v] + weight) {
        d[to] = d[v] + weight;
        pq.emplace(d[to], to);
      }
    }
  }
  return d;
}

Max asked Wesley for a test case that caused this solution to TLE, but Wesley refused, so Max asked you.

Generate a graph that causes this implementation of Dijkstra's for the Single Source Shortest Path Problem to have the variable counter exceed ~10^7~.

Can you strengthen the test data before the contest?

Constraints

~1 \le N \le 10^5~

~0 \le M \le \min(2 \times 10^5, \frac{N \times (N-1)}{2})~

~1 \le u, v \le N~

~u \ne v~

~1 \le w \le 10^9~

There are no duplicate edges.

Output Specification

Output the number of nodes in the graph, ~N~, and the number of edges in the graph, ~M~, on the first line.

For the next ~M~ lines, output an undirected edge from ~u~ to ~v~ with a weight of ~w~.

Sample Output

5 3
1 2 5
1 3 7
1 5 2

Explanation for Sample Output

This solution has ~N = 5~ and ~M = 3~. Note that this solution does not receive AC since it does not cause the above implementation to exceed the counter constraints.