#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()
 
#define REP(i,s,e)	for(int i=(s); i<(e); i++)
#define rep(i,n)	REP(i,0,n)
#define REPE(i,s,e)	for(int i=s; i>e; i--)
#define repe(i,n)	REPE(i,n,-1)


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<vi> vvi;
 
const int IMAX=((1<<30)-1)*2+1;
const int INF=100000000;
const double EPS=1e-10;
//int mod=1000000007
 


int main(){
	int n;
	while(cin >> n && n>0){
		int a,b,sa=0,sb=0;
		rep(i,n){
			cin>>a>>b;
			if(a>b) sa+=(a+b);
			else if(a==b) sa+=a,sb+=b;
			else sb+=(a+b);
		}
		cout<<sa<<" "<<sb<<endl;
	}
}
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int sb[10][10000];

#define MAX (50000000)

int main(){
  int n,k;
  while(scanf("%d%d",&n,&k), n+k){
    int dist[n][n];
    REP(i,n) REP(j,n) dist[i][j] = MAX;
    REP(i,n) dist[i][i] = 0;
    while(k --> 0){
      int s; scanf("%d",&s);
      if(s == 0){
        int a,b;
        scanf("%d%d",&a,&b); a--; b--;
        if(dist[a][b] == MAX) puts("-1");
        else printf("%d\n",dist[a][b]);
      }else{
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c); a--; b--;
        if(dist[a][b] < c) continue;
        dist[a][b] = dist[b][a] = c;
        REP(i,n){
          dist[a][i] = dist[i][a] = min(dist[a][i], dist[a][b] + dist[b][i]);
          dist[b][i] = dist[i][b] = min(dist[b][i], dist[b][a] + dist[a][i]);
        }
        REP(i,n) REP(j,n){
          dist[i][j] = min(dist[i][j], dist[i][a] + dist[a][j]);
          dist[i][j] = min(dist[i][j], dist[i][b] + dist[b][j]);
        }
      }
    }
  }
  return 0;
}