Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm looks so similar to the Dijkstra's algorithm after replacing the FIFO queue with priority queue, and shows you the below pseudo code.

By picking the best vertex from we mean picking the vertex with the smallest priority value (in case that multiple vertices have the smallest priority value, pick the vertex with the largest index among them).

You, the future computer scientist, find the BaoBao-modified SPFA algorithm works so slow in some carefully construted graph. However, BaoBao is sure that his algorithm works well, unless you show him a simple undirected graph that makes the variable cnt in the SPFA function no less than a certain at some time. For convenience the source vertex of the SPFA function is specified to be vertex .

Just teach him a lesson!

输入描述:

There is only one test case in each test file.
The first and only line of the input contains a single integer  where  for the sample test case and  for the only secret test case.

输出描述:

Output several lines in the following format to describe the input data of a simple undirected graph that makes the variable cnt in the SPFA function no less than  at some time.
The first line contains two integers  () and  (), indicating the number of vertices and edges in the graph.
Then  lines follow, the -th of which contains three integers ,  () and  (), indicating that the -th edge in the graph has a weight of  and connects the -th and the -th vertices.
Note that a simple graph contains no self-loops and no multiple edges.

1

4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6

备注:

 For your convenience, you can copy the C++ code, which corresponds to the given pseudo code, from the contest website. Save the code as spfa.cpp, use g++ spfa.cpp -O2 -o spfa to compile it and you will get an executable file named spfa. Run spfa, feed your output to its standard input and it will print out the final value of cnt. Given the sample output it will print out , which means the sample output is not sufficient to pass the secret test case. 
 
 Note that the given code does not check the validity of your output (for example it does not check if your output is really a simple graph). You might still fail the test if your output is invalid, even if the executable prints out a large value. 
 
 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=105;
const int INF=0x3f3f3f3f;

vector<pair<int, int> > e[MAXN];
int dis[MAXN], vis[MAXN];

void spfa(int n) {
    for(int i=1; i<=n; i++)
        dis[i]=INF, vis[i]=0;

    priority_queue<pair<int, int> > pq;
    dis[1]=0, vis[1]=1;
    pq.push(make_pair(-dis[1], 1));

    int cnt=0;
    while (!pq.empty()) {
        int u=pq.top().second;
        pq.pop();
        vis[u]=0, ++cnt;
        for (size_t i=0; i<e[u].size(); i++) {
            int v=e[u][i].first, w=e[u][i].second;
            if (dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                if (vis[v]==0) {
                    pq.push({-dis[v], v});
                    vis[v]=1;
                }
            }
        }
    }
    printf("%d\n",cnt);
}

int main() {
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i=1; i<=m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].push_back(make_pair(v, w));
        e[v].push_back(make_pair(u, w));
    }
    spfa(n);
    return 0;
}