#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n, m, i, j, temp; cin >> n >> m;
    vector<pair<long long, long long>> way, minx(n), miny(n);
    vector<vector<long long>> dp(n, vector<long long>(m)), a(n, vector<long long>(m)), px(n, vector<long long>(m, -1)), py(n, vector<long long>(m, -1));
    for(i=0; i<n; ++i) for(j=0; j<m; ++j) cin >> a[i][j];
    miny[0]={a[0][0], 0};
    dp[0][0]=a[0][0];
    minx[0]={a[0][0], 0};
    for(i=1; i<m; ++i){
        dp[0][i]=miny[0].first+a[0][i];
        px[0][i]=miny[0].second;
        py[0][i]=0;
        if(dp[0][i]<miny[0].first){
            miny[0].first=dp[0][i];
            miny[0].second=i;
        }
        minx[i]={dp[0][i], 0};
    }
    for(i=1; i<n; ++i){
        dp[i][0]=minx[0].first+a[i][0];
        px[i][0]=0;
        py[i][0]=minx[0].second;
        if(dp[i][0]<minx[0].first){
            minx[0].first=dp[i][0];
            minx[0].second=i;
        }
        miny[i]={dp[i][0], 0};
    }
    for(i=1; i<n; ++i) for(j=1; j<m; ++j){
        if(minx[j].first<miny[i].first){
            dp[i][j]=minx[j].first+a[i][j];
            px[i][j]=j;
            py[i][j]=minx[j].second;
        } else{
            dp[i][j]=miny[i].first+a[i][j];
            px[i][j]=miny[i].second;
            py[i][j]=i;
        }
        if(dp[i][j]<miny[i].first){
            miny[i].first=dp[i][j];
            miny[i].second=j;
        }
        if(dp[i][j]<minx[j].first){
            minx[j].first=dp[i][j];
            minx[j].second=i;
        }
    }
    for(i=n-1, j=m-1; i!=-1&&j!=-1; temp=i, i=py[i][j], j=px[temp][j]) way.push_back({i, j});
    reverse(way.begin(), way.end());
    cout << dp[n-1][m-1] << " " << way.size() << "\n";
    for(i=0; i<way.size(); ++i) cout << way[i].first+1 << " " << way[i].second+1 << "\n";
    return 0;
}