udebug的数据都可以通过，但WA了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define REP(i,s,e) for(int i=s;i>=e;i--)
#define LL long long
#define U unsigned
const int N=110;
int m,n,a[N][N],dp[N][N],last[N][N],sz;
string s[N];
queue<int> qx,qy;
void add(int x,int y){
	if(last[x][y]!=-1)add(x-1,last[x][y]);
	s[sz]+='0'+y-1;
}
int main(){
	while(scanf("%d%d",&m,&n)==2){
		rep(i,1,m)rep(j,1,n)scanf("%d",a[j]+i);
		if(m==1){
			int cnt=0;
			rep(i,1,n)printf("1 "),cnt+=a[i][1];
			printf("\n%d\n",cnt);
			continue; 
		}
		rep(i,1,n){
			dp[i][1]=min(dp[i-1][m],min(dp[i-1][1],dp[i-1][2]))+a[i][1];
			rep(j,2,m-1)dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+a[i][j];
			dp[i][m]=min(dp[i-1][1],min(dp[i-1][m],dp[i-1][m-1]))+a[i][m];
		}
		memset(last,0,sizeof(last));
		rep(i,1,m)qx.push(1),qy.push(i),last[1][i]=-1;
		while(!qx.empty()){
			int x=qx.front(),y=qy.front();qx.pop(),qy.pop();
			int d[3]={y-1,y,y+1};
			if(y==1)d[0]=1,d[1]=2,d[2]=m;
			if(y==m)d[0]=1,d[1]=m-1,d[2]=m;
			rep(i,0,2)if(!last[x+1][d[i]]&&dp[x][y]+a[x+1][d[i]]==dp[x+1][d[i]])last[x+1][d[i]]=y,qx.push(x+1),qy.push(d[i]);
		}
		int ans=2e9;sz=0;
		rep(i,1,m)ans=min(ans,dp[n][i]);
		rep(i,1,m)if(dp[n][i]==ans)s[++sz]="a",add(n,i);
		sort(s+1,s+1+sz);
		rep(i,1,n)printf("%d ",s[1][i]-'0'+1);
		printf("\n%d\n",ans);
	}
	return 0;
}