Andrew prefers taxi to other means of transport, but recently most taxi drivers have been acting inappropriately. In order to earn more money, taxi drivers started to drive in circles. Roads in Andrew's city are one-way, and people are not necessary able to travel from one part to another, but it pales in comparison to insidious taxi drivers.

The mayor of the city decided to change the direction of certain roads so that the taxi drivers wouldn't be able to increase the cost of the trip endlessly. More formally, if the taxi driver is on a certain crossroads, they wouldn't be able to reach it again if he performs a nonzero trip.

Traffic controllers are needed in order to change the direction the road goes. For every road it is known how many traffic controllers are needed to change the direction of the road to the opposite one. It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads.

You need to calculate the minimum number of traffic controllers that you need to hire to perform the task and the list of the roads that need to be reversed.

Input

The first line contains two integers nn and mm (2≤n≤1000002≤n≤100000, 1≤m≤1000001≤m≤100000) — the number of crossroads and the number of roads in the city, respectively.

Each of the following mm lines contain three integers uiui, vivi and cici (1≤ui,vi≤n1≤ui,vi≤n, 1≤ci≤1091≤ci≤109, ui≠viui≠vi) — the crossroads the road starts at, the crossroads the road ends at and the number of traffic controllers required to reverse this road.

Output

In the first line output two integers the minimal amount of traffic controllers required to complete the task and amount of roads kk which should be reversed. kkshould not be minimized.

In the next line output kk integers separated by spaces — numbers of roads, the directions of which should be reversed. The roads are numerated from 11 in the order they are written in the input. If there are many solutions, print any of them.

Examples

Input

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

Output

2 2
1 3

Input

5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

Output

3 3
3 4 7

题意：给你一个有向图，然后里面有环，让你翻转一些边，让这个图无环

要求最大反向边的权值最小

题解：二分搜索权值mid，然后通过拓扑排序检查大于mid的边能不能围成圈

然后 看一下边权小于mid的边的拓扑序，如果起点的拓扑序大于重点的拓扑序，就翻转

这样能保证翻转的边也不能构成环

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 100000+5
using namespace std;
int n,m;
vector<int>e[maxn],ansid;
queue <int>q;
int ind[maxn];
int tp[maxn],tot;
struct edge {
    int u,v,c;
}ed[maxn];
void init(){
    for(int i=1;i<=n;i++){
        e[i].clear();
        ind[i]=0;
    }
    tot=0;
}
void topu(){
    for(int i=1;i<=n;i++){
        if(ind[i]==0){
            tp[i]=tot++;
            q.push(i);
        }
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        int size=e[t].size();
        for(int i=0;i<size;i++){
            int to=e[t][i];
            ind[to]--;
            if(ind[to]==0){
                q.push(to);
                tp[to]=tot++;
            }
        }
    }
}
int check(int mid){
    init();
    for(int i=1;i<=m;i++){
        if(ed[i].c>mid){
            e[ed[i].u].push_back(ed[i].v);
            ind[ed[i].v]++;
        }
    }
    topu();
    for(int i=1;i<=n;i++){
          if(ind[i]>0)return false;
    }
    ansid.clear();
    for(int i=1;i<=m;i++){
        if(ed[i].c<=mid&&tp[ed[i].u]>tp[ed[i].v])ansid.push_back(i);
    }
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].c);
    }
    int l=0,r=1e9,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    int minn=0;
    int size=ansid.size();
    for(int i=0;i<size;i++){
        minn=max(minn,ed[ansid[i]].c);
    }
    printf("%d %d\n",minn,size);
    for(int i=0;i<size;i++)
    {
        printf("%d ",ansid[i]);
    }
}