#include <iostream>
using namespace std;

int shops[100005][3];
int dp[100005][3];

int shopping(int item, int i, int n)
{
	if (dp[i][item] != -1)
		return dp[i][item];

	if (i == n - 1)
	{
		dp[i][item] = shops[i][item];

		return dp[i][item];
	}
	else
	{
		dp[i][item] = shops[i][item] + min(shopping((item + 1) % 3, i + 1, n),
				shopping((item + 2) % 3, i + 1, n));

		return dp[i][item];
	}
}

int main()
{
	int t, n;

	cin >> t;

	while (t--)
	{
		cin >> n;

		for (int i = 0; i < n; i++)
			dp[i][0] = dp[i][1] = dp[i][2] = -1;

		for (int i = 0; i < n; i++)
			cin >> shops[i][0] >> shops[i][1] >> shops[i][2];

		int minimum = min(shopping(0, 0, n), shopping(1, 0, n));
		minimum = min(shopping(2, 0, n), minimum);

		cout << minimum << endl;
	}

	return 0;
}
Language: C++