#include <bits/stdc++.h>
#define watch(x) cout <<(#x)<<" is "<<(x)<<endl
#define debug cout <<"hi"<<endl
#define maxn 3e5+10
#define inf32 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int,int>pii;
const int MOD=1e9+7;
const int INF32=1<<30;
const ll INF64=1LL<<60;

ll lowbit(int x) {return x&(-x);}
vector<ll>sum(maxn,0);

void update(int i,int x){
    while(i<sum.size()){
        sum[i] += x;
        i += lowbit(i);
    }
}
//记得index要从1开始
ll query(int i){
    ll ans = 0;
    while(i>0){
       ans += sum[i];
       i -= lowbit(i);
    }
    return ans;
}

void solve(){
    int h,w,m;cin >> h >> w >> m;
    vector<ll>x(m),y(m),sc(w+1,h+1),rc(h+1,w+1);
    for(int i = 0;i<m;i++){
        cin >> x[i] >> y[i];
        rc[x[i]] = min(rc[x[i]],y[i]);
        sc[y[i]] = min(sc[y[i]],x[i]);
    }
    ll ans = 0;
    vector<pll>a(m);
    for(int i = 0;i<m;i++) a[i].first = x[i],a[i].second = y[i];
    sort(a.begin(),a.end());
    ll lim = w+1;
    vector<bool>b(w+1,0);
    int j = 0;
    for(int i = 1;i<=h;i++){
        ll tp = rc[i]-1;
        if(tp==0) break;
        ans += tp;
        update(1,1);
        update(rc[i],-1);
        while(j<m&&a[j].first==i){
            if(a[j].first==1) lim = min(lim,a[j].second);
            if(a[j].second<lim){
                    if(b[a[j].second]==0){
                        b[a[j].second] = 1;
                        ans += a[j].first-1-query(a[j].second);//watch(a[j].first-1-query(a[j].first));
                    }
            }
            j++;
        }
    }
        for(int i = 1;i<lim;i++){
            if(!b[i]){
                ans += sc[i]-1-query(i);
            }
        }
        cout << ans;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  solve();
  return 0;
}


#include <bits/stdc++.h>
/* #include <atcoder/all> */

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;
/* using namespace atcoder; */

using ll = long long;
using P = pair<int, int>;

const ll INF = 1 << 30;

template<class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

struct Data {
  int to;
  ll cost;
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> dist(n, INF);
//  vector<vector<ll>> G2(n, vector<ll>(n, INF));
  vector<vector<Data>> G(n, vector<Data>());
  rep(i, m) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    if (a == b) {
      chmin(dist.at(a), c);
    } else {
//      chmin(G2.at(a).at(b), c);
      Data d = {b, c};
      G.at(a).push_back(d);
    }
  }
//  vector<vector<Data>> G(n, vector<Data>());
//  rep(i, n) {
//    rep(j, n) {
//      if (i == j) continue;
//      Data d = {j, G2.at(i).at(j)};
//      G.at(i).push_back(d);
//    }
//  }

  vector<vector<ll>> dist2(n, vector<ll>(n, INF));
  rep(i, n) {
    vector<ll> dist3(n, INF);
    dist3.at(i) = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>,
        greater<pair<ll, int>>> que;
    que.push(make_pair(dist3.at(i), i));
    while (!que.empty()) {
      int v = que.top().second;
      ll d = que.top().first;
      que.pop();
      if (d > dist3.at(v)) continue;
      for (auto e : G.at(v)) {
        if (e.to == i) {
          continue;
        }
        if (chmin(dist3.at(e.to), dist3.at(v) + e.cost)) {
          que.push(make_pair(dist3.at(e.to), e.to));
        }
      }
    }
    rep(j, n) {
//      cerr << dist3.at(j) << " ";
      dist2.at(i).at(j) = dist3.at(j);
    }
//    cerr << endl;
  }
  rep(i, n) {
    rep(j, n) {
      if (i == j) continue;
      dist.at(i) = min(dist.at(i), dist2.at(i).at(j) + dist2.at(j).at(i));
    }
  }
  rep(i, n) {
    cout << ((dist.at(i) == INF) ? -1 : dist.at(i)) << endl;
  }
  return 0;
}
