#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;


void calc(vector<int> &ans,int n,int dist[100][100]);

int main(void){
  
  int cases;
  int dist[100][100];
  int n,count;
  vector<pair<int,int> > edges[100];
  bool found[100];
  cin >> cases;
  while(cases--){
    cin >> n >> count;
    int a,b,c;
    // fill edges
    for(int i=0;i<n;i++){
      edges[i].clear();
    }
    while(count--){
      cin >> a >> b >> c;
      edges[a-1].push_back(make_pair(b-1,c));
      edges[b-1].push_back(make_pair(a-1,c));
    }
    // dijkstra -- fill dist.
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	dist[i][j] = INT_MAX;
	found[j] = false;
      }
      dist[i][i] = 0;
      found[i] = true;
      int t = i;
      for(int j=0;j<n-1;j++){
	for(int k=0;k<edges[t].size();k++){
	  if(dist[i][edges[t][k].first] > dist[i][t] + edges[t][k].second){
	    dist[i][edges[t][k].first] = dist[i][t] + edges[t][k].second;
	  }
	}
	int min_trg,min_len = INT_MAX;
	for(int k=0;k<n;k++){
	  if(found[k]) continue;
	  if(dist[i][k] < min_len){
	    min_len = dist[i][k];
	    min_trg = k;
	  }
	}
	t = min_trg;
	found[min_trg] = true;
      }
    }
    //search answer.
    vector<int> ans;
    calc(ans,n,dist);
    cout << ans[0];
    for(int i=1;i<ans.size();i++){
      cout << " " << ans[i];
    }
    cout << endl;
    
  }
  return 0;
}

void calc(vector<int> &ans,int n,int dist[100][100]){
  pair<int,int> data[100];
  vector<int> tmp_v;
  int best_score = INT_MAX;
  int score;
  int trg;
  int total;
  tmp_v.resize(n);
  for(int h1=0;h1<n;h1++){
    for(int h2=h1+1;h2<n;h2++){
      trg = 0;
      total = 0;
      for(int i=0;i<n;i++){
	if(i==h1 || i == h2){
	  tmp_v[i] = 0;
	  continue;
	}
	tmp_v[i] = h1+1;
	data[trg] = make_pair(dist[i][h2]-dist[i][h1],i);
	trg++;
	total += dist[i][h1];
      }
      sort(data,data+trg);
      score = dist[h1][h2] * 1 * (n-1) + total * (n-1);
      if(score < best_score){
	best_score = score;
	ans = tmp_v;
      }else if(score == best_score && ans > tmp_v){
	ans = tmp_v;
      }
      for(int i=0;i<n-2;i++){
	tmp_v[data[i].second] = h2 +1;
	total += data[i].first;
	score = dist[h1][h2] * (i+2) * (n-i-2) + total * (n-1);
	if(score < best_score){
	  best_score = score;
	  ans = tmp_v;
	}else if(score == best_score && ans > tmp_v){
	  ans = tmp_v;
	}
      }
    }
  }
}