题目描述

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 $Q$ 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 $\tt{cnt}$ in the SPFA function no less than a certain $k$ $\textbf{at some time}$. For convenience, the source vertex of the SPFA function is specified to be vertex $1$.

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 $k$ where $k = 1$ for the sample test case and $k = 10^5$ 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 $\tt{cnt}$ in the SPFA function no less than $k$ $\textbf{at some time}$.

The first line contains two integers $n$ ($1 \le n \le 100$) and $m$ ($0 \le m \le 10^3$), indicating the number of vertices and edges in the graph.

Then $m$ lines follow, the $i$-th of which contains three integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and $w_i$ ($1 \le w_i \le 10^6$), indicating that the $i$-th edge in the graph has a weight of $w_i$ and connects the $u_i$-th and the $v_i$-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 $\tt{C++}$ code, which corresponds to the given pseudo code, from the contest website. Save the code as $\tt{spfa.cpp}$, use $\text{g++ spfa.cpp -O2 -o spfa}$ to compile it and you will get an executable file named $\tt{spfa}$. Run $\tt{spfa}$, feed your output to its standard input and it will print out the $\textbf{final}$ value of $\tt{cnt}$. Given the sample output it will print out $4$, 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.