Problem: graphs_as_a_service (2019 round1)

With a successful commission under his belt, Carlos has really made a splash
with his consulting firm, Carlos Structures Industries. His next customer is
Texas Instruments, the well-known manufacturer of graphing calculators.

_ "In today's competitive environment, you need an edge. I can make sure that
your newest graphing calculator is chock-full of the best modern graphs." _

Carlos's pitch seems to have worked as Texas Instruments has ordered an
undirected, weighted graph. Their R&D department has come up with a list of
requirements that will ensure the graph is a hit with Gen Z schoolchildren.

To start with, the graph must have **N** nodes numbered 1 to **N**. It must
have no self-loops and at most one edge connecting each unordered pair of
nodes. The weight of each edge must be an integer between 1 and 1,000,000,
inclusive. The graph does not need to be connected.

The graph must also satisfy **M** customer requirements, the _i_th of which
states that the shortest distance between two different nodes **Xi** and
**Yi** must be equal to **Zi**. No two requirements pertain to the same
unordered pair of nodes.

Carlos's goal is to find any valid graph consistent with all of these
requirements if possible, or to determine that no such graph exists.

### Input

Input begins with an integer **T**, the number of graphs that Texas
Instruments has commissioned. For each graph, there is first a line containing
the space-separated integers **N** and **M**. Then, **M** lines follow, the
_i_th of which contains the space-separated integers **Xi**, **Yi**, and
**Zi**.

### Output

For the _i_th graph, print a line containing "Case #_i_: " followed by either
an integer **E** and then a description of a valid graph if possible, or the
string "Impossible" if no valid graph exists.

A graph description contains **E** lines, where **E** is the number of edges
in your graph. The _i_th line contains the space-separated integers **Ai**,
**Bi**, and **Wi** indicating that there is an edge between nodes **Ai** and
**Bi** with weight **Wi**. Please keep in mind that your graph must satisfy
all of the requirements stated above (both the fundamental requirements
dictated by Texas Instruments, and the **M** customer ones).

### Constraints

1 ≤ **T** ≤ 350  
2 ≤ **N** ≤ 50  
1 ≤ **M** ≤ 1,000  
1 ≤ **Xi**, **Yi** ≤ **N**  
**Xi** ≠ **Yi**   
1 ≤ **Zi** ≤ 1,000,000  

### Explanation of Sample

In the graph described by the first sample case's sample output, the shortest
distance between nodes 3 and 1 is 5 (along the path 3 -> 2 -> 1), as required.
**Multiple other outputs would also be accepted for this case.**

**Multiple other outputs would also be accepted for the third and fourth cases.**



Sample input:
5
3 1
3 1 5
3 3
1 2 1
2 3 1
1 3 100
4 3
1 4 5
2 3 5
4 2 4
8 10
2 6 16
7 3 6
5 1 11
7 6 12
8 1 8
6 1 18
1 3 12
3 5 9
6 5 15
7 1 6
10 10
6 7 7
8 5 3
3 7 7
10 4 24
6 2 8
8 7 19
3 9 22
5 7 17
9 2 12
2 7 2


Sample output:
Case #1: 3
1 2 4
1 3 8
3 2 1
Case #2: Impossible
Case #3: 4
1 2 3
2 4 4
4 3 3
3 1 2
Case #4: 8
7 2 4
8 5 5
1 5 11
6 8 10
8 7 2
1 7 6
3 8 4
5 7 9
Case #5: Impossible



Code: // Graphs as a Service
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,M;
	int i,j,k;
	int X[1000],Y[1000],Z[1000];
	int dist[50][50];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			Fill(dist,60);
			// input
			Read(N),Read(M);
				Fox(i,M)
				{
					Read(X[i]),Read(Y[i]),Read(Z[i]),X[i]--,Y[i]--;
					dist[X[i]][Y[i]]=dist[Y[i]][X[i]]=Z[i];
				}
			// Floyd's
				Fox(i,N)
					Fox(j,N)
						Fox(k,N)
							Min(dist[j][k],dist[j][i]+dist[i][k]);
			// check validity, and output
			printf("Case #%d: ",t);
				Fox(i,M)
					if (dist[X[i]][Y[i]]!=Z[i])
					{
						printf("Impossible\n");
						goto Done;
					}
			printf("%d\n",M);
				Fox(i,M)
					printf("%d %d %d\n",X[i]+1,Y[i]+1,Z[i]);
Done:;
		}
	return(0);
}