#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 200011;
struct one{int t,x,y;}a[MAXN];
int fx[MAXN],diff=0;
int place(int val){return std::lower_bound(fx+1,fx+diff+1,val)-fx;}
struct sgt
{
	struct node
	{
		ll cnt,sum;
	}t[MAXN<<2|1];
#define rt t[num]
	void modify(un pos,ll k,un l=1,un r=diff,un num=1)
	{
		rt.cnt+=k,rt.sum+=k*fx[pos];
		if(l==r)return;
		un mid=(l+r)>>1;
		if(pos<=mid)modify(pos,k,l,mid,num<<1);
		else modify(pos,k,mid+1,r,num<<1|1);
	}
	ll Qcnt(un ql,un qr,un l=1,un r=diff,un num=1)
	{
		if(ql>qr)return 0;
		if(ql<=l&&r<=qr)return rt.cnt;
		un mid=(l+r)>>1;
		ll res=0;
		if(ql<=mid)res+=Qcnt(ql,qr,l,mid,num<<1);
		if(qr>mid)res+=Qcnt(ql,qr,mid+1,r,num<<1|1);
		return res;
	}
	ll Qsum(un ql,un qr,un l=1,un r=diff,un num=1)
	{
		if(ql>qr)return 0;
		if(ql<=l&&r<=qr)return rt.sum;
		un mid=(l+r)>>1;
		ll res=0;
		if(ql<=mid)res+=Qsum(ql,qr,l,mid,num<<1);
		if(qr>mid)res+=Qsum(ql,qr,mid+1,r,num<<1|1);
		return res;
	}
}t[2];
int seq[2][MAXN];
ll f[2][MAXN];
int main()
{
	int n1=read(),n2=read(),m=read();
	fx[++diff]=0;
	for(int i=1;i<=m;++i)a[i].t=read()-1,a[i].x=read(),fx[++diff]=a[i].y=read();
	std::sort(fx+1,fx+diff+1),diff=std::unique(fx+1,fx+diff+1)-fx-1;
	t[0].modify(1,n1),t[1].modify(1,n2);
	for(int i=1;i<=n1;++i)seq[0][i]=1;
	for(int i=1;i<=n2;++i)seq[1][i]=1;
	ll ans=0;
	for(int i=1;i<=m;++i)
	{
		int tp=a[i].t,val=place(a[i].y);
		int& pre=seq[tp][a[i].x];
		///printf("%d to %d(%d)\n",pre,val,a[i].y);
		if(pre<=val)
		{
			//printf("%d\n",a[i].y-fx[pre]);
			ans+=t[!a[i].t].Qcnt(1,pre)*(a[i].y-fx[pre])+ t[!a[i].t].Qcnt(pre+1,val)*a[i].y-t[!a[i].t].Qsum(pre+1,val);
		}
		else
		{
			ans-=t[!a[i].t].Qcnt(1,val)*(fx[pre]-a[i].y)+ t[!a[i].t].Qcnt(val+1,pre)*fx[pre]-t[!a[i].t].Qsum(val+1,pre);
		}
		t[a[i].t].modify(pre,-1);
		t[a[i].t].modify(pre=val,1);
		printf("%lld\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define fi first
#define se second
#define Mp make_pair
#define pb push_back

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
mt19937 mrand(time(0));
#define debug(...) fprintf(stderr, __VA_ARGS__)
ll get(ll r) { return ((ll)mrand() * mrand() % r + r) % r; }
ll get(ll l, ll r) { return get(r - l + 1) + l; }

int n, m, dis[100100], head[100100], tot, v[100100];
struct Edge {
    int to, nxt, c, d, sd;
    int f(int t) {
        t = max(t, sd - 1);
        return c + d / (t + 1) + t;
    }
} e[200100];
void addEdge(int a, int b, int c, int d) {
    e[++tot] = (Edge){ b, head[a], c, d, (int)round(sqrt(d))}, head[a] = tot;
    e[++tot] = (Edge){ a, head[b], c, d, (int)round(sqrt(d))}, head[b] = tot;
}
signed main() {
    scanf("%lld %lld", &n, &m);
    for(int i = 1, a, b, c, d; i <= m; i++) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        addEdge(a, b, c, d);
    }
    memset(dis, 0x3f, sizeof(dis)); dis[1] = 0;
    priority_queue<pii> q; q.push(pii(0, 1)); // <-val, pos>
    while(q.size()) {
        pii x = q.top(); q.pop();
        if(v[x.se]) continue; v[x.se] = 1;
        for(int i = head[x.se]; i; i = e[i].nxt) {
            int y = e[i].to;
            if(dis[y] > e[i].f(-x.fi)) {
                dis[y] = e[i].f(-x.fi);
                q.push(pii(-dis[y], y));
            }
        }
    }
    printf("%lld\n", dis[n] > 1e18 ? -1 : dis[n]);
    debug("time=%.4f\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}