#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

class BIT {
public:
	int size_ = 1;
	vector<long long> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, long long x) {
		pos++;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	long long sum(int pos) {
		long long s = 0; pos++;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

long long N, M, Q;
long long T[1 << 19], X[1 << 19], Y[1 << 19];
long long A[1 << 19], B[1 << 19];
vector<long long> Z;

BIT A1, A2;
BIT B1, B2;

void change1(int p1, int p2) {
	A1.add(A[p1], -1);
	A2.add(A[p1], -Z[A[p1]]);
	A[p1] = p2;
	A1.add(A[p1], 1);
	A2.add(A[p1], Z[A[p1]]);
}

void change2(int p1, int p2) {
	B1.add(B[p1], -1);
	B2.add(B[p1], -Z[B[p1]]);
	B[p1] = p2;
	B1.add(B[p1], 1);
	B2.add(B[p1], Z[B[p1]]);
}

int main() {
	// Input
	cin >> N >> M >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> T[i] >> X[i] >> Y[i];
		Z.push_back(Y[i]);
	}
	Z.push_back(0);
	sort(Z.begin(), Z.end());
	Z.erase(unique(Z.begin(), Z.end()), Z.end());

	// Lower Bound
	for (int i = 1; i <= Q; i++) {
		Y[i] = lower_bound(Z.begin(), Z.end(), Y[i]) - Z.begin();
	}

	// BIT Init
	A1.init(Z.size()); A1.add(0, N);
	A2.init(Z.size());
	B1.init(Z.size()); B1.add(0, M);
	B2.init(Z.size());

	// Query
	long long CurrentAns = 0;
	for (int i = 1; i <= Q; i++) {
		if (T[i] == 1) {
			long long pos1 = A[X[i]];
			long long pos2 = Y[i];
			long long sa1 = 1LL * Z[pos2] * B1.sum(pos2) - 1LL * Z[pos1] * B1.sum(pos1);
			long long sa2 = 1LL * (B2.sum(Z.size() + 1) - B2.sum(pos2)) - 1LL * (B2.sum(Z.size() + 1) - B2.sum(pos1));
			CurrentAns += (sa1 + sa2);
			change1(X[i], Y[i]);
		}
		if (T[i] == 2) {
			long long pos1 = B[X[i]];
			long long pos2 = Y[i];
			long long sa1 = 1LL * Z[pos2] * A1.sum(pos2) - 1LL * Z[pos1] * A1.sum(pos1);
			long long sa2 = 1LL * (A2.sum(Z.size() + 1) - A2.sum(pos2)) - 1LL * (A2.sum(Z.size() + 1) - A2.sum(pos1));
			CurrentAns += (sa1 + sa2);
			change2(X[i], Y[i]);
		}
		cout << CurrentAns << endl;
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<ll> v;
vector<pair<ll,ll> > aj[2005];
bool vis[2005];
ll dist[2005];
priority_queue<pair<ll,ll> ,vector<pair<ll,ll> > ,greater<pair<ll,ll> > > pq;
ll dijkstra(ll x,ll n){
	memset(vis,false,sizeof(vis));
	ll maxn = 2e9,a,b;
	for(int i=1;i<=n;i++)dist[i] = 2e9;
	pq.push(make_pair(0,x));
	while(pq.size()){
		a = pq.top().first;
		b = pq.top().second;
		pq.pop();
		if(vis[b])continue;
		vis[b] = true;
		for(auto v:aj[b]){
			if(v.first==x){
				maxn = min(maxn,v.second+a);
//				cout<<a<<" "<<b<<" "<<v.first<<" "<<v.second<<" hi\n";	
			}
			if(dist[v.first]>a+v.second){
				dist[v.first] = a+v.second;
				pq.push(make_pair(dist[v.first],v.first));
			}
		}
	}
	return maxn;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,m,i,a,b,c,j,k,t,q,sum = 0,cnt = 0,maxn = 0,ans = 0,X,Y,Z;
	cin>>n>>m;
	for(i=0;i<m;i++){
		cin>>a>>b>>c;
		aj[a].push_back(make_pair(b,c));
	}
	for(i=1;i<=n;i++){
		a = dijkstra(i,n);
		if(a==2e9)cout<<"-1\n";
		else cout<<a<<"\n";
	}
}