Even though he isn‘t a student of computer science, Por Costel the pig has started to study Graph Theory. Today he‘s learning about Bellman-Ford, an algorithm that calculates the minimum cost path from a source node (for instance, node 1) to all the other nodes in a directed graph with weighted edges. Por Costel, utilizing his scarce programming knowledge has managed to scramble the following code in C++, a variation of the Bellman-Ford algorithm:

You can notice a lot of deficiencies in the above code. In addition to its rudimentary documentation, we can see that Por Costel has stored this graph as an array of edges (the array ). An edge is stored as the triplet  signifying an edge that spans from  to  and has weight . But even worse is the fact that the algorithm is SLOW!

As we want our hooved friend to walk away with a good impression about computer science, we want his code to execute as FAST as possible. In order to do so, we can modify the order of edges in the array  so that the while loop executes a small number of times.

Given a directed graph of  nodes and  edges, you are asked to produce an ordering of the edges such that the Bellman-Ford algorithm written by Por Costel should finish after at most two iterations of the while loop(that is, the program should enter the while loop at most twice).

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
#define INF 1000000000007ll
#define N 100010
#define M 200010
struct Point{ll d;int u;
Point(const ll &X,const int &Y){d=X;u=Y;}
Point(){}};
int T,n,m;
int cnt;
bool operator < (Point a,Point b){return a.d>b.d;}
priority_queue<Point>q;
int v[M],__next[M],first[N],w[M],e;
int fa[N],fam[N];
ll d[N];
void AddEdge(int U,int V,int W)
{
	v[++e]=V;
	w[e]=W;
	__next[e]=first[U];
	first[U]=e;
}
bool vis[N],intree[M];
void dijkstra(int S)
{
    for(int i=1;i<=n;++i) d[i]=INF;
    d[S]=0; q.push(Point(0,S));
    while(!q.empty())
      {
        Point x=q.top(); q.pop();
        if(!vis[x.u])
          {
            vis[x.u]=1;
            for(int i=first[x.u];i;i=__next[i])
              if(d[v[i]]>d[x.u]+(ll)w[i])
                {
                  d[v[i]]=d[x.u]+(ll)w[i];
                  fa[v[i]]=x.u;
                  intree[fam[v[i]]]=0;
                  fam[v[i]]=i;
                  intree[i]=1;
                  q.push(Point(d[v[i]],v[i]));
                }
          }
      }
}
void dfs(int U)
{
	for(int i=first[U];i;i=__next[i])
	  if(intree[i])
	    {
	      ++cnt;
	      printf("%d%c",i,cnt==m ? ‘\n‘ : ‘ ‘);
	      dfs(v[i]);
	    }
}
int main()
{
	freopen("algoritm.in","r",stdin);
	freopen("algoritm.out","w",stdout);
	//freopen("b.in","r",stdin);
	int x,y,z;
	scanf("%d",&T);
	for(;T;--T)
	  {
	  	cnt=e=0;
	  	memset(v,0,sizeof(v));
	  	memset(w,0,sizeof(w));
	  	memset(__next,0,sizeof(__next));
	  	memset(first,0,sizeof(first));
	  	memset(fa,0,sizeof(fa));
	  	memset(fam,0,sizeof(fam));
	  	memset(d,0,sizeof(d));
	  	memset(vis,0,sizeof(vis));
	  	memset(intree,0,sizeof(intree));
	  	scanf("%d%d",&n,&m);
	  	for(int i=1;i<=m;++i)
	  	  {
	  	  	scanf("%d%d%d",&x,&y,&z);
	  	  	AddEdge(x,y,z);
	  	  }
	  	dijkstra(1);
	  	dfs(1);
	  	for(int i=1;i<=m;++i)
	  	  if(!intree[i])
	  	    {
	  	      ++cnt;
	  	      printf("%d%c",i,cnt==m ? ‘\n‘ : ‘ ‘);
	  	    }
	  }
	return 0;
}