#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxN = 1e3 + 100;
const int maxM = 1e3 + 100;
const int inf = 1e15;

int from[maxM], to[maxM], w[maxM];
int st[maxN], en[maxN], ans[maxN];
int n, m;

void print(){
  return;
  cerr << "st: \n";
  for(int i = 0; i < n; i++)
    cerr << st[i] << ' ';
  cerr << endl;
  cerr << "en: \n";
  for(int i = 0; i < n; i++)
    cerr << en[i] << ' ';
  cerr << endl;
  cerr << endl; 
}

void relax(bool ez_sag){  
  for(int i = 0; i < m; i++){
    int u = from[i], v = to[i] , x = w[i];
    if(ez_sag){
      if(st[u] > x + st[v])
	st[u] = -inf;
      if(en[v] > x + en[u])
	en[v] = -inf;
    } else {
      st[u] = min(st[u], x + st[v]);
      en[v] = min(en[v], x + en[u]);
    }
  }
  print();
}

int32_t main(){
  int t;
  cin >> t;
  while(t--){
    memset(st, 0, sizeof st);
    memset(en, 0, sizeof en);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
      cin >> from[i] >> to[i] >> w[i], from[i]--, to[i]--;
    for(int i = 0; i < 2*n; i++)
      relax(false);
    for(int i = 0; i < n; i++)
      ans[i] = st[i] + en[i];
    for(int i = 0; i < 2*n; i++)
      relax(true);
    for(int i = 0; i < n; i++)
      if (ans[i] == st[i] + en[i])
	cout << st[i] + en[i] << '\n';
      else
	  cout << "INF" << '\n';
    //    cout << '\n';
  }
}