#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 100000000;

int cost[101][101];
int d[101];
bool used[101];
int n,k;

int dijkstra(int s, int g) {
  fill(d,d+n,INF);
  fill(used,used+n,false);
  d[s] = 0;

  while(true) {
    int v = -1;
    
    for (int u = 0; u < n; u++ ) {
      if (!used[u] && ( v == -1 || d[u] < d[v])) v = u;
    }

    if (v == -1) break;
    used[v] = true;

    for (int u = 0; u < n; u++ ) {
      d[u] = min(d[u],d[v] + cost[v][u]);
    }
  }
  if ( d[g] == INF ) return INF;
  else return d[g];

}

int main() {
  while (cin >> n >> k, n||k) {
    for ( int i = 0; i < n; i++ ) {
      for ( int j = 0; j < n; j++ ) {
	cost[i][j] = INF;
      }
    }
    for ( int i = 0; i < k; i++ ) {
      int order; cin >> order;
      if ( order == 0 ) {
	int a,b; cin >> a >> b;
	a--; b--;
	int ans = dijkstra(a,b);
	if ( ans == INF ) cout << -1 << endl;
	else cout << ans << endl;
      } else if ( order == 1 ) {
	int c,d,e; cin >> c >> d >> e;
	c--; d--;
	cost[c][d] = min(e,cost[c][d]);
	cost[d][c] = min(e,cost[d][c]);
      }
    
    }
  }
  return 0;
}
#include<iostream>
using namespace std;

class meb{
public:
	int num;
	unsigned long long tanka;
	unsigned long long count;
	unsigned long long sum;
};

int main(){
	int n;
	while(1){
		int cc=0;
		cin>>n;
		meb st[n];
		if(n==0)break;
		for(int i=0;i<n;i++){
			cin>>st[i].num>>st[i].tanka>>st[i].count;
		}
		for(int k=0;k<n;k++){
			st[k].sum=st[k].tanka*st[k].count;
		}
		for(int j=0;j<n;j++){
			for(int l=j+1;l<n;l++){
				if(st[j].num==st[l].num){
					(st[j].sum)=(st[j].sum)+(st[l].sum);
					st[l].sum=0;
				}
			}
		}
		for(int a=0;a<n;a++){
			if(st[a].sum>=1000000)cout<<st[a].num<<endl;
			else cc++;
		}
		if(cc==n)cout<<"NA"<<endl;
	}
	return 0;
}