#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const string debug_line = "yolo";
const long long linf = 1e15 + 5;
const int BLOCK = 330;
struct answerType {
  int val;
  vector<int> edges;

 public:
  answerType() {
    val = INT_MAX;
    edges.clear();
  };
  answerType(int _val, vector<int> _edges) {
    val = _val;
    edges = _edges;
  };
  void reset() {
    val = 0;
    edges.clear();
  }
};
struct solve {
  bool visited[1010];
  int component[1010];
  int arr[1010];
  bool isbridge[30010];
  vector<pair<pair<int, int>, int> > Adj[1010];
  queue<int> Q[1010];
  int comp2[1010];
  vector<int> tree[1010];
  int P[1010][36];
  int level1[1010];
  vector<pair<pair<pair<int, int>, int>, int> > edges;
  int s;
  int t;
  int ignoreEdge;
  int n;
  int m;
  answerType answer;
  int comcount;
  int countPairNodes;
  map<pair<int, int>, int> mp1;
  vector<int> edgeList[30010];
  int dfs_timer;
  solve() {
    s = -1;
    t = -1;
    ignoreEdge = -1;
    edges.clear();
    n = -1;
    m = -1;
    countPairNodes = 0;
    comcount = 0;
    dfs_timer = 0;
  };
  solve(int _s, int _t, int _ignoreEdge,
        vector<pair<pair<pair<int, int>, int>, int> > _edges, int _n, int _m) {
    s = _s;
    t = _t;
    n = _n;
    m = _m;
    countPairNodes = 0;
    comcount = 0;
    ignoreEdge = _ignoreEdge;
    edges = _edges;
    dfs_timer = 0;
    for (int(i) = (0); (i) < (n + 1); ++(i)) {
      Adj[i].clear();
      visited[i] = false;
    }
    for (int(i) = (0); (i) < (m + 1); ++(i)) {
      isbridge[i] = false;
    }
    for (auto &(t1) : (edges)) {
      if (t1.second != ignoreEdge) {
        Adj[t1.first.first.first].push_back(make_pair(
            make_pair(t1.first.first.second, t1.first.second), t1.second));
        Adj[t1.first.first.second].push_back(make_pair(
            make_pair(t1.first.first.first, t1.first.second), t1.second));
      }
    }
    answer.val = INT_MAX;
    answer.edges.clear();
  };

 public:
  int DFS(int u, int p, int edge) {
    visited[u] = true;
    component[u] = comcount;
    arr[u] = dfs_timer++;
    int dbe = arr[u];
    for (auto &(t1) : (Adj[u])) {
      if (!visited[t1.first.first] && t1.first.first != p) {
        dbe = min(dbe, DFS(t1.first.first, u, t1.second));
      } else if (edge != t1.second) {
        dbe = min(dbe, arr[t1.first.first]);
      }
    }
    if (dbe == arr[u] && edge != -1) {
      isbridge[edge] = true;
    }
    return dbe;
  };
  void DFS1(int u) {
    int curcmp = comcount;
    Q[curcmp].push(u);
    visited[u] = true;
    while (!Q[curcmp].empty()) {
      int v = Q[curcmp].front();
      comp2[v] = curcmp;
      Q[curcmp].pop();
      for (auto &(t1) : (Adj[v])) {
        if (visited[t1.first.first]) {
          continue;
        } else if (isbridge[t1.second]) {
          comcount++;
          tree[curcmp].push_back(comcount);
          tree[comcount].push_back(curcmp);
          DFS1(t1.first.first);
        } else {
          Q[curcmp].push(t1.first.first);
          visited[t1.first.first] = true;
        }
      }
    }
  };
  void DFS2(int u, int p) {
    visited[u] = true;
    P[u][0] = p;
    level1[u] = level1[p] + 1;
    for (int(i) = (1); (i) < (35); ++(i)) {
      P[u][i] = P[P[u][i - 1]][i - 1];
    }
    for (auto &(t1) : (tree[u])) {
      if (!visited[t1]) {
        DFS2(t1, u);
      }
    }
  };
  int LCA(int u, int v) {
    if (level1[u] < level1[v]) {
      swap(u, v);
    }
    for (int(i) = (34); (i) > (-1); --(i)) {
      if (level1[P[u][i]] >= level1[v]) {
        u = P[u][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int(i) = (34); (i) > (-1); --(i)) {
      if (P[u][i] != P[v][i]) {
        u = P[u][i];
        v = P[v][i];
      }
    }
    return P[u][0];
  };
  void fillListNodes(vector<pair<int, int> > &listNodes, int s, int t) {
    int lca = LCA(s, t);
    if (lca == s) {
      int currNode = t;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    } else if (lca == t) {
      int currNode = s;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    } else {
      int currNode = s;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
      currNode = t;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    }
  };
  void findAnswer() {
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        DFS(i, 0, -1);
        comcount++;
      }
    }
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        DFS1(i);
      }
    }
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        level1[i] = 0;
        DFS2(i, i);
      }
    }
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
    }
    for (auto &(t1) : (edges)) {
      if (isbridge[t1.second]) {
        if (level1[comp2[t1.first.first.first]] <
            level1[comp2[t1.first.first.second]]) {
          swap(t1.first.first.first, t1.first.first.second);
        }
        if (mp1.count(make_pair(comp2[t1.first.first.first],
                                comp2[t1.first.first.second])) == 0) {
          mp1[make_pair(comp2[t1.first.first.first],
                        comp2[t1.first.first.second])] = countPairNodes++;
        }
        assert(level1[comp2[t1.first.first.first]] -
                   level1[comp2[t1.first.first.second]] ==
               1);
        edgeList[mp1[make_pair(comp2[t1.first.first.first],
                               comp2[t1.first.first.second])]]
            .push_back(t1.second);
      }
    }
    if (component[s] != component[t]) {
      if (ignoreEdge == -1) {
        answer.val = 0;
        answer.edges.clear();
      } else {
        answer.val = edges[ignoreEdge].first.second;
        answer.edges = {ignoreEdge + 1};
      }
      return;
    } else {
      int s1 = s;
      int t1 = t;
      s1 = comp2[s1];
      t1 = comp2[t1];
      if (s1 == t1) {
        answer.val = INT_MAX;
        answer.edges.clear();
        return;
      }
      int lca = LCA(s1, t1);
      vector<pair<int, int> > listNodes;
      fillListNodes(listNodes, s1, t1);
      answerType temp;
      bool poss = false;
      for (auto &(t1) : (listNodes)) {
        if (edgeList[mp1[t1]].size() == 1) {
          answerType currentAnswer;
          if (ignoreEdge == -1) {
            poss = true;
            currentAnswer.val = edges[edgeList[mp1[t1]][0]].first.second;
            currentAnswer.edges = {edgeList[mp1[t1]][0] + 1};
          } else {
            poss = true;
            currentAnswer.val = edges[edgeList[mp1[t1]][0]].first.second +
                                edges[ignoreEdge].first.second;
            currentAnswer.edges = {edgeList[mp1[t1]][0] + 1, ignoreEdge + 1};
          }
          if (currentAnswer.val < answer.val) {
            answer = currentAnswer;
          }
        }
      }
      if (!poss) {
        answer.val = INT_MAX;
        answer.edges.clear();
      }
    }
  };
};
vector<pair<pair<pair<int, int>, int>, int> > edges;
vector<pair<pair<int, int>, int> > Adj[1010];
bool visited[1010];
vector<int> answerPath;
answerType answer;
vector<int> path;
void DFSPath(int u, int p, int end1) {
  visited[u] = true;
  if (u == end1) {
    answerPath = path;
  }
  for (auto &(t1) : (Adj[u])) {
    if (!visited[t1.first.first] && t1.first.first != p) {
      path.push_back(t1.second);
      DFSPath(t1.first.first, u, end1);
      path.pop_back();
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int s, t;
  scanf("%d%d", &s, &t);
  for (int(i) = (0); (i) < (m); ++(i)) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    edges.push_back(make_pair(make_pair(make_pair(a, b), c), i));
    Adj[a].push_back(make_pair(make_pair(b, c), i));
    Adj[b].push_back(make_pair(make_pair(a, c), i));
  }
  solve tryAll = solve(s, t, -1, edges, n, m);
  tryAll.findAnswer();
  if (tryAll.answer.val < answer.val) {
    answer = tryAll.answer;
  }
  DFSPath(s, 0, t);
  for (auto &(t1) : (answerPath)) {
    solve tryAll = solve(s, t, t1, edges, n, m);
    tryAll.findAnswer();
    if (tryAll.answer.val < answer.val) {
      answer = tryAll.answer;
    }
  }
  if (answer.val == INT_MAX) {
    printf("-1\n");
  } else {
    printf("%d\n", answer.val);
    printf("%d\n", (int)answer.edges.size());
    for (auto &(t1) : (answer.edges)) {
      printf("%d ", t1);
    }
    printf("\n");
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

Again, there are hard times in Berland! Many towns have such tensions that even civil war is possible. 

There are n towns in Reberland, some pairs of which connected by two-way roads. It is not guaranteed that it is possible to reach one town from any other town using these roads. 

Towns s and t announce the final break of any relationship and intend to rule out the possibility of moving between them by the roads. Now possibly it is needed to close several roads so that moving from s to t using roads becomes impossible. Each town agrees to spend money on closing no more than one road, therefore, the total number of closed roads will be no more than two.

Help them find set of no more than two roads such that there will be no way between s and t after closing these roads. For each road the budget required for its closure was estimated. Among all sets find such that the total budget for the closure of a set of roads is minimum.

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 30 000) — the number of towns in Berland and the number of roads.

The second line contains integers s and t (1 ≤ s, t ≤ n, s ≠ t) — indices of towns which break up the relationships.

Then follow m lines, each of them contains three integers xi, yi and wi (1 ≤ xi, yi ≤ n, 1 ≤ wi ≤ 109) — indices of towns connected by the i-th road, and the budget on its closure.

All roads are bidirectional. It is allowed that the pair of towns is connected by more than one road. Roads that connect the city to itself are allowed. 

Output

In the first line print the minimum budget required to break up the relations between s and t, if it is allowed to close no more than two roads.

In the second line print the value c (0 ≤ c ≤ 2) — the number of roads to be closed in the found solution.

In the third line print in any order c diverse integers from 1 to m — indices of closed roads. Consider that the roads are numbered from 1 to m in the order they appear in the input. 

If it is impossible to make towns s and t disconnected by removing no more than 2 roads, the output should contain a single line -1. 

If there are several possible answers, you may print any of them.

Examples

Input

6 7
1 6
2 1 6
2 3 5
3 4 9
4 6 4
4 6 5
4 5 1
3 1 3


Output

8
2
2 7


Input

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


Output

9
2
4 5


Input

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


Output

1
1
2


Input

2 3
1 2
1 2 734458840
1 2 817380027
1 2 304764803


Output

-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const string debug_line = "yolo";
const long long linf = 1e15 + 5;
const int BLOCK = 330;
struct answerType {
  int val;
  vector<int> edges;

 public:
  answerType() {
    val = INT_MAX;
    edges.clear();
  };
  answerType(int _val, vector<int> _edges) {
    val = _val;
    edges = _edges;
  };
  void reset() {
    val = 0;
    edges.clear();
  }
};
struct solve {
  bool visited[1010];
  int component[1010];
  int arr[1010];
  bool isbridge[30010];
  vector<pair<pair<int, int>, int> > Adj[1010];
  queue<int> Q[1010];
  int comp2[1010];
  vector<int> tree[1010];
  int P[1010][36];
  int level1[1010];
  vector<pair<pair<pair<int, int>, int>, int> > edges;
  int s;
  int t;
  int ignoreEdge;
  int n;
  int m;
  answerType answer;
  int comcount;
  int countPairNodes;
  map<pair<int, int>, int> mp1;
  vector<int> edgeList[30010];
  int dfs_timer;
  solve() {
    s = -1;
    t = -1;
    ignoreEdge = -1;
    edges.clear();
    n = -1;
    m = -1;
    countPairNodes = 0;
    comcount = 0;
    dfs_timer = 0;
  };
  solve(int _s, int _t, int _ignoreEdge,
        vector<pair<pair<pair<int, int>, int>, int> > _edges, int _n, int _m) {
    s = _s;
    t = _t;
    n = _n;
    m = _m;
    countPairNodes = 0;
    comcount = 0;
    ignoreEdge = _ignoreEdge;
    edges = _edges;
    dfs_timer = 0;
    for (int(i) = (0); (i) < (n + 1); ++(i)) {
      Adj[i].clear();
      visited[i] = false;
    }
    for (int(i) = (0); (i) < (m + 1); ++(i)) {
      isbridge[i] = false;
    }
    for (auto &(t1) : (edges)) {
      if (t1.second != ignoreEdge) {
        Adj[t1.first.first.first].push_back(make_pair(
            make_pair(t1.first.first.second, t1.first.second), t1.second));
        Adj[t1.first.first.second].push_back(make_pair(
            make_pair(t1.first.first.first, t1.first.second), t1.second));
      }
    }
    answer.val = INT_MAX;
    answer.edges.clear();
  };

 public:
  int DFS(int u, int p, int edge) {
    visited[u] = true;
    component[u] = comcount;
    arr[u] = dfs_timer++;
    int dbe = arr[u];
    for (auto &(t1) : (Adj[u])) {
      if (!visited[t1.first.first] && t1.first.first != p) {
        dbe = min(dbe, DFS(t1.first.first, u, t1.second));
      } else if (edge != t1.second) {
        dbe = min(dbe, arr[t1.first.first]);
      }
    }
    if (dbe == arr[u] && edge != -1) {
      isbridge[edge] = true;
    }
    return dbe;
  };
  void DFS1(int u) {
    int curcmp = comcount;
    Q[curcmp].push(u);
    visited[u] = true;
    while (!Q[curcmp].empty()) {
      int v = Q[curcmp].front();
      comp2[v] = curcmp;
      Q[curcmp].pop();
      for (auto &(t1) : (Adj[v])) {
        if (visited[t1.first.first]) {
          continue;
        } else if (isbridge[t1.second]) {
          comcount++;
          tree[curcmp].push_back(comcount);
          tree[comcount].push_back(curcmp);
          DFS1(t1.first.first);
        } else {
          Q[curcmp].push(t1.first.first);
          visited[t1.first.first] = true;
        }
      }
    }
  };
  void DFS2(int u, int p) {
    visited[u] = true;
    P[u][0] = p;
    level1[u] = level1[p] + 1;
    for (int(i) = (1); (i) < (35); ++(i)) {
      P[u][i] = P[P[u][i - 1]][i - 1];
    }
    for (auto &(t1) : (tree[u])) {
      if (!visited[t1]) {
        DFS2(t1, u);
      }
    }
  };
  int LCA(int u, int v) {
    if (level1[u] < level1[v]) {
      swap(u, v);
    }
    for (int(i) = (34); (i) > (-1); --(i)) {
      if (level1[P[u][i]] >= level1[v]) {
        u = P[u][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int(i) = (34); (i) > (-1); --(i)) {
      if (P[u][i] != P[v][i]) {
        u = P[u][i];
        v = P[v][i];
      }
    }
    return P[u][0];
  };
  void fillListNodes(vector<pair<int, int> > &listNodes, int s, int t) {
    int lca = LCA(s, t);
    if (lca == s) {
      int currNode = t;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    } else if (lca == t) {
      int currNode = s;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    } else {
      int currNode = s;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
      currNode = t;
      while (currNode != lca) {
        listNodes.push_back(make_pair(currNode, P[currNode][0]));
        currNode = P[currNode][0];
      }
    }
  };
  void findAnswer() {
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        DFS(i, 0, -1);
        comcount++;
      }
    }
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        DFS1(i);
      }
    }
    memset(visited, 0, sizeof(visited));
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
      if (!visited[i]) {
        level1[i] = 0;
        DFS2(i, i);
      }
    }
    for (int(i) = (1); (i) < (n + 1); ++(i)) {
    }
    for (auto &(t1) : (edges)) {
      if (isbridge[t1.second]) {
        if (level1[comp2[t1.first.first.first]] <
            level1[comp2[t1.first.first.second]]) {
          swap(t1.first.first.first, t1.first.first.second);
        }
        if (mp1.count(make_pair(comp2[t1.first.first.first],
                                comp2[t1.first.first.second])) == 0) {
          mp1[make_pair(comp2[t1.first.first.first],
                        comp2[t1.first.first.second])] = countPairNodes++;
        }
        assert(level1[comp2[t1.first.first.first]] -
                   level1[comp2[t1.first.first.second]] ==
               1);
        edgeList[mp1[make_pair(comp2[t1.first.first.first],
                               comp2[t1.first.first.second])]]
            .push_back(t1.second);
      }
    }
    if (component[s] != component[t]) {
      if (ignoreEdge == -1) {
        answer.val = 0;
        answer.edges.clear();
      } else {
        answer.val = edges[ignoreEdge].first.second;
        answer.edges = {ignoreEdge + 1};
      }
      return;
    } else {
      int s1 = s;
      int t1 = t;
      s1 = comp2[s1];
      t1 = comp2[t1];
      if (s1 == t1) {
        answer.val = INT_MAX;
        answer.edges.clear();
        return;
      }
      int lca = LCA(s1, t1);
      vector<pair<int, int> > listNodes;
      fillListNodes(listNodes, s1, t1);
      answerType temp;
      bool poss = false;
      for (auto &(t1) : (listNodes)) {
        if (edgeList[mp1[t1]].size() == 1) {
          answerType currentAnswer;
          if (ignoreEdge == -1) {
            poss = true;
            currentAnswer.val = edges[edgeList[mp1[t1]][0]].first.second;
            currentAnswer.edges = {edgeList[mp1[t1]][0] + 1};
          } else {
            poss = true;
            currentAnswer.val = edges[edgeList[mp1[t1]][0]].first.second +
                                edges[ignoreEdge].first.second;
            currentAnswer.edges = {edgeList[mp1[t1]][0] + 1, ignoreEdge + 1};
          }
          if (currentAnswer.val < answer.val) {
            answer = currentAnswer;
          }
        }
      }
      if (!poss) {
        answer.val = INT_MAX;
        answer.edges.clear();
      }
    }
  };
};
vector<pair<pair<pair<int, int>, int>, int> > edges;
vector<pair<pair<int, int>, int> > Adj[1010];
bool visited[1010];
vector<int> answerPath;
answerType answer;
vector<int> path;
void DFSPath(int u, int p, int end1) {
  visited[u] = true;
  if (u == end1) {
    answerPath = path;
  }
  for (auto &(t1) : (Adj[u])) {
    if (!visited[t1.first.first] && t1.first.first != p) {
      path.push_back(t1.second);
      DFSPath(t1.first.first, u, end1);
      path.pop_back();
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int s, t;
  scanf("%d%d", &s, &t);
  for (int(i) = (0); (i) < (m); ++(i)) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    edges.push_back(make_pair(make_pair(make_pair(a, b), c), i));
    Adj[a].push_back(make_pair(make_pair(b, c), i));
    Adj[b].push_back(make_pair(make_pair(a, c), i));
  }
  solve tryAll = solve(s, t, -1, edges, n, m);
  tryAll.findAnswer();
  if (tryAll.answer.val < answer.val) {
    answer = tryAll.answer;
  }
  DFSPath(s, 0, t);
  for (auto &(t1) : (answerPath)) {
    solve tryAll = solve(s, t, t1, edges, n, m);
    tryAll.findAnswer();
    if (tryAll.answer.val < answer.val) {
      answer = tryAll.answer;
    }
  }
  if (answer.val == INT_MAX) {
    printf("-1\n");
  } else {
    printf("%d\n", answer.val);
    printf("%d\n", (int)answer.edges.size());
    for (auto &(t1) : (answer.edges)) {
      printf("%d ", t1);
    }
    printf("\n");
  }
  return 0;
}

```