Baltazar

#include <bits/stdc++.h>

using namespace std;

const int kN = 3e5;
const int64_t INF = 1e18L;
const int MODS = 4;
const int mod[] = {805306457, (int)1e9 + 7, (int)1e9 + 9, 1610612741};
int n, m;
vector<pair<int, int>> g[1 + kN];
int cnt[2][1 + kN][2][4];
int64_t dp[2][1 + kN][2];

void addSelf(int &x, int y, int mod) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int mult(int x, int y, int mod) {
  return (int64_t)x * y % mod;
}

void Dijkstra(int source, int t) {
  for (int v = 1; v <= n; ++v) {
    dp[t][v][0] = dp[t][v][1] = INF;
    for (int i = 0; i < MODS; ++i) {
      cnt[t][v][0][i] = cnt[t][v][1][i] = 0;
    }
  }

  dp[t][source][0] = 0;
  for (int i = 0; i < MODS; ++i) {
    cnt[t][source][0][i] = 1;
  }

  priority_queue<tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<tuple<int64_t, int, int>>> pq;
  pq.emplace(0, source, 0);

  while (!pq.empty()) {
    int64_t cost;
    int u;
    int par;
    tie(cost, u, par) = pq.top();
    pq.pop();

    if (cost != dp[t][u][par]) {
      continue;
    }

    for (const auto &it : g[u]) {
      int v, w;
      tie(v, w) = it;

      int64_t newCost = cost + w;
      int newPar = (par + w) % 2;

      if (newCost < dp[t][v][newPar]) {
        dp[t][v][newPar] = newCost;
        for (int i = 0; i < MODS; ++i) {
          cnt[t][v][newPar][i] = cnt[t][u][par][i];
        }
        pq.emplace(newCost, v, newPar);
      } else if (newCost == dp[t][v][newPar]) {
        for (int i = 0; i < MODS; ++i) {
          addSelf(cnt[t][v][newPar][i], cnt[t][u][par][i], mod[i]);
        }
      }
    }
  }
}

void testCase() {
  cin >> n >> m;

  for (int v = 1; v <= n; ++v) {
    g[v].clear();
  }

  vector<tuple<int, int, int>> edges;

  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;

    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);

    edges.emplace_back(u, v, w);
  }

  Dijkstra(1, 0);
  Dijkstra(n, 1);

  int64_t bestPath = INF;
  int bestCounts[MODS];
  int goodPar = -1;

  for (int p = 0; p < 2; ++p) {
    if (dp[0][n][p] < bestPath) {
      goodPar = p;
      bestPath = dp[0][n][p];

      for (int i = 0; i < MODS; ++i) {
        bestCounts[i] = cnt[0][n][p][i];
      }
    }
  }

  int64_t secondBest = dp[0][n][goodPar ^ 1];
  int secondCounts[MODS];
  for (int i = 0; i < MODS; ++i) {
    secondCounts[i] = cnt[0][n][goodPar ^ 1][i];
  }

  if (secondBest != bestPath + 1) {
    cout << "0\n\n";
    return;
  }

  vector<int> sol;

  for (int i = 0; i < m; ++i) {
    int u, v, w;
    tie(u, v, w) = edges[i];

    int64_t shortestPath = INF;
    int paths[4];
    int secondPaths[MODS] = {0, 0, 0, 0};

    for (const int &first : {u, v}) {
      int second = u + v - first;

      for (int p1 = 0; p1 < 2; ++p1) {
        for (int p2 = 0; p2 < 2; ++p2) {
          int64_t len = dp[0][first][p1] + w + dp[1][second][p2];

          if (len < shortestPath) {
            shortestPath = len;

            for (int j = 0; j < MODS; ++j) {
              paths[j] = mult(cnt[0][first][p1][j], cnt[1][second][p2][j], mod[j]);
            }
          } else if (len == shortestPath) {
            for (int j = 0; j < MODS; ++j) {
              addSelf(paths[j], mult(cnt[0][first][p1][j], cnt[1][second][p2][j], mod[j]), mod[j]);
            }
          }

          if (len == bestPath + 1) {
            for (int j = 0; j < MODS; ++j) {
              addSelf(secondPaths[j], mult(cnt[0][first][p1][j], cnt[1][second][p2][j], mod[j]), mod[j]);
            }
          }
        }
      }
    }

    if (shortestPath != bestPath) {
      continue;
    }

    bool ok = true;

    for (int j = 0; j < MODS && ok; ++j) {
      if (paths[j] != bestCounts[j]) {
        ok = false;
      }
    }

    if (!ok) {
      continue;
    }

    ok = false;

    for (int j = 0; j < MODS && !ok; ++j) {
      if (secondCounts[j] != secondPaths[j]) {
        ok = true;
      }
    }

    if (ok) {
      sol.emplace_back(i + 1);
    }
  }

  cout << sol.size() << '\n';

  for (const int &id : sol) {
    cout << id << ' ';
  }

  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int tests;
  cin >> tests;

  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }

  return 0;
}