ll@h----,@w,@a[h][w];
DijkstraHeap<ll>d;
d.malloc(h*w,1);
rep(y,h){
	if(a[y][0]>=0){
		d.change(y*w,a[y][0]);
	}
}
while(d.size){
	ll b=d.pop();
	ll y=b/w;
	ll x=b%w;
	if(x<w-1){
		rep(v,y-1,y+2){
			if(v>=0&&v<h){
				rep(u,x-1,x+2){
					if(u>=0&&a[v][u]>=0){
						d.change(v*w+u,d.val[b]+a[v][u]);
					}
				}
			}
		}
	}
}
ll z=1<<30;
rep(y,h){
	if(d.visited[y*w+(w-1)]){
		z<?=d.val[y*w+(w-1)];
	}
}
wt(z>>30?-1:z);