116

#include <iostream>
#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;
int input[11][101];
int dp[11][101];
int next_row[11][101];

int main()
{
	int tmp,temp_position,row;

	while(scanf("%d%d",&r,&c)==2)
	{
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				cin>>input[i][j];

		for(int i=0;i<r;i++)
			dp[i][c-1]=input[i][c-1];

		for(int i=c-2;i>=0;i--)
		{
			for(int j=0;j<r;j++)
			{
				tmp=MX;

				for(int k=-1;k<=1;k++)
				{
					temp_position = (j+k+r)%r;

					if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))
					{
						next_row[j][i]=temp_position;
						tmp = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}

 

#include <iostream>
#include <cstdio>

#define MX 100000000

using namespace std;

int r,c;
int input[11][101];
int dp[11][101];
int next_row[11][101];

int main()
{
	int tmp,temp_position,row;

	while(scanf("%d%d",&r,&c)==2)
	{
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				cin>>input[i][j];

		for(int i=0;i<r;i++)
			dp[i][c-1]=input[i][c-1];

		for(int i=c-2;i>=0;i--)
		{
			for(int j=0;j<r;j++)
			{
				tmp=MX;

				for(int k=-1;k<=1;k++)
				{
					temp_position = (j+k+r)%r;

					if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i]))
					{
						next_row[j][i]=temp_position;
						tmp = dp[temp_position][i+1];
					}
				}
				dp[j][i]=input[j][i]+tmp;
			}
		}

		tmp = MX;

		for(int i=0;i<r;i++)
		{
			if(tmp>dp[i][0])
			{
				tmp = dp[i][0];
				row = i;
			}
		}
		cout<<row+1;

		for(int i=0;i<c-1;i++)
		{
			row = next_row[row][i];
			cout<<" "<<row+1;
		}
		cout<<"\n"<<tmp<<"\n";
	}

	return 0;
}