#include <iostream>
#include <iomanip>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <array>
#include <numeric>
#include <limits>
#include <cstdlib>
#include <fstream>

// BGL includes
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/tuple/tuple.hpp>


#define unless(X) if(!(X))

// BGL graph definitions
// =====================
// Graph Type with nested interior edge properties for Flow Algorithms
typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS> traits;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property,
    boost::property<boost::edge_capacity_t, long,
        boost::property<boost::edge_residual_capacity_t, long,
            boost::property<boost::edge_reverse_t, traits::edge_descriptor> > > >   graph;
// Interior Property Maps
typedef boost::graph_traits<graph>::edge_descriptor         edge_desc;
typedef boost::graph_traits<graph>::out_edge_iterator           out_edge_it;


class edge_adder {
  graph &G;

 public:
  explicit edge_adder(graph &G) : G(G) {}

  void add_edge(int from, int to, long capacity) {
    auto c_map = boost::get(boost::edge_capacity, G);
    auto r_map = boost::get(boost::edge_reverse, G);
    const auto e = boost::add_edge(from, to, G).first;
    const auto rev_e = boost::add_edge(to, from, G).first;
    c_map[e] = capacity;
    c_map[rev_e] = 0; // reverse edge has no capacity!
    r_map[e] = rev_e;
    r_map[rev_e] = e;
  }
};




std::tuple<std::vector<bool>, int, int> cut_set(graph G, int N, int src, int sink)
{
    int flow = boost::push_relabel_max_flow(G, src, sink);
    auto rc_map = boost::get(boost::edge_residual_capacity, G);

    int card = 1;
    // BFS to find vertex set S
    std::vector<bool> vis(N, false); // visited flags
    std::queue<int> Q; // BFS queue (from std:: not boost::)
    vis[src] = true; // Mark the source as visited
    Q.push(src);
    while (!Q.empty()) {
        const int u = Q.front();
        Q.pop();
        out_edge_it ebeg, eend;
        for (boost::tie(ebeg, eend) = boost::out_edges(u, G); ebeg != eend; ++ebeg) {
            const int v = boost::target(*ebeg, G);
            // Only follow edges with spare capacity
            if (rc_map[*ebeg] == 0 || vis[v]) continue;
            vis[v] = true;
            card++;
            Q.push(v);
        }
    }
    return std::make_tuple(vis, flow, card);
}

void testCase() {
  int n, m;
  std::cin >> n >> m;
  graph G(n);
  edge_adder adder(G);


    int u, v, c;
  for (int i = 0; i < m; i++)
  {
        std::cin >> u >> v >> c;
        adder.add_edge(u, v, c);
  }

    int cost, nbFigures;
    std::vector<bool> set;
    std::tie(set, cost, nbFigures) = cut_set(G, n, 0, n-1);

    std::cout << cost << std::endl;
    std::cout << nbFigures << " ";
    for (int i = 0; i < n; i++)
        if (set[i]) std::cout << i << " ";

  std::cout << std::endl;
}




int main() {
  std::ios_base::sync_with_stdio(false);

  int t; std::cin >> t;
  for (int i = 0; i < t; i++)
  {
    testCase();
  }

}