#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <time.h>#include <stdlib.h>#include <string>#include <bitset>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <sstream>#include <stack>#include <iomanip>using namespace std;#define pb push_back#define mp make_pairtypedef pair<int,int> pii;typedef long long ll;typedef double ld;typedef vector<int> vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#ifdef LOCAL#define TIMER cerr<<clock()<<"ms\n"#else#define TIMER#endif#define SZ 1234567int n,m,k,N=0;int xs[SZ],ys[SZ],ts[SZ];typedef pair<int,int> pii;map<pii,int> sta;bool cmp2(pii a,pii b){    if(a.se!=b.se) return a.se<b.se;    return a.fi<b.fi;}pii ps[SZ]; int pn=0;pii ss[SZ],rs[SZ];int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};void rec(int a,int b){    if(sta[pii(a,b)]==1) return;    if(a<1||b<1||a>n||b>m) return;    ps[++pn]=pii(a,b);}int ls(pii a) {return lower_bound(ps+1,ps+1+pn,a)-ps;}int S,T;int qs[SZ];int dist[SZ];#undef SZ#define SZ 1234567Edgvoid conn(pii a,pii b){    if(a==b) return;    ad_de(ls(a),ls(b));}void spfa(){    int h=0,t=0;    qs[t++]=S; dist[S]=1;    while(h^t)    {        int x=qs[h++];        for es(x,e)        {            int b=vb[e];            if(dist[b]) continue;            dist[b]=dist[x]+1;            qs[t++]=b;        }    }}int main(){    FO(ice)    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=k;i++)    {        scanf("%d%d%d",xs+i,ys+i,ts+i);        sta[pii(xs[i],ys[i])]=ts[i]+1;    }    rec(1,1); rec(n,m);    rec(1,m); rec(n,1);    for(int i=1;i<=k;i++)    {        rec(xs[i],1); rec(xs[i],m);        rec(1,ys[i]); rec(n,ys[i]);        rec(xs[i]+1,1); rec(xs[i]+1,m);        rec(xs[i]-1,1); rec(xs[i]-1,m);        rec(1,ys[i]+1); rec(n,ys[i]+1);        rec(1,ys[i]-1); rec(n,ys[i]-1);        rec(xs[i],ys[i]);        for(int j=0;j<4;j++)        rec(xs[i]+dx[j],ys[i]+dy[j]);    }    sort(ps+1,ps+1+pn);    pn=unique(ps+1,ps+1+pn)-ps-1;    int sn=0,rn=0;    for(int i=1;i<=k;i++)    {        if(ts[i]==0) ss[++sn]=pii(xs[i],ys[i]);        else rs[++rn]=pii(xs[i],ys[i]);    }    ss[++sn]=pii(-2000000000,-2000000000);    ss[++sn]=pii(2000000000,2000000000);    rs[++rn]=pii(-2000000000,-2000000000);    rs[++rn]=pii(2000000000,2000000000);    sort(ss+1,ss+1+sn); sort(rs+1,rs+1+rn);    //先处理左右     for(int i=1;i<=pn;i++)    {        int x=ps[i].fi,y=ps[i].se;        pii cur=pii(x,y);        if(y!=1) //L        {        int maxn=1;        int id=lower_bound(rs+1,rs+1+rn,cur)-rs-1;        pii ns=rs[id];        if(ns.fi==x) maxn=max(maxn,ns.se);        id=lower_bound(ss+1,ss+1+sn,cur)-ss-1;        ns=ss[id];        if(ns.fi==x) maxn=max(maxn,ns.se+1);        conn(cur,pii(x,maxn));        }        if(y!=m) //R        {        int minn=m;        int id=upper_bound(rs+1,rs+1+rn,cur)-rs;        pii ns=rs[id];        if(ns.fi==x) minn=min(minn,ns.se);        id=upper_bound(ss+1,ss+1+sn,cur)-ss;        ns=ss[id];        if(ns.fi==x) minn=min(minn,ns.se-1);        conn(cur,pii(x,minn));        }    }    sort(ss+1,ss+1+sn,cmp2); sort(rs+1,rs+1+rn,cmp2);    for(int i=1;i<=pn;i++)    {        int x=ps[i].fi,y=ps[i].se;        pii cur=pii(x,y);        if(x!=1) //U        {        int maxn=1;        int id=lower_bound(rs+1,rs+1+rn,cur,cmp2)-rs-1;        pii ns=rs[id];        if(ns.se==y) maxn=max(maxn,ns.fi);        id=lower_bound(ss+1,ss+1+sn,cur,cmp2)-ss-1;        ns=ss[id];        if(ns.se==y) maxn=max(maxn,ns.fi+1);        conn(cur,pii(maxn,y));        }        if(x!=n) //R        {        int minn=n;        int id=upper_bound(rs+1,rs+1+rn,cur,cmp2)-rs;        pii ns=rs[id];        if(ns.se==y) minn=min(minn,ns.fi);        id=upper_bound(ss+1,ss+1+sn,cur,cmp2)-ss;        ns=ss[id];        if(ns.se==y) minn=min(minn,ns.fi-1);        conn(cur,pii(minn,y));        }    }    S=ls(pii(1,1));T=ls(pii(n,m));    spfa(); cout<<dist[T]-1<<"\n";}