1. import java.io.BufferedWriter;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.OutputStreamWriter;
  6. import java.io.PrintWriter;
  7. import java.io.Writer;
  8. import java.util.Arrays;
  9. import java.util.InputMismatchException;
  10.  
  11. class SamuAndShopping
  12. {
  13. static int t, n;
  14. static int shops[][], dp[][];
  15. static InputReader in;
  16. static OutputWriter out;
  17. public static void main(String[] args)
  18. {
  19. in = new InputReader(System.in);
  20. out = new OutputWriter(System.out);
  21. solve();
  22. out.flush();
  23. in.close();
  24. out.close();
  25. }
  26. static void solve()
  27. {
  28. t = in.nextInt();
  29. for (int i = 0; i < t; i++)
  30. {
  31. n = in.nextInt();
  32.  
  33. shops = new int[n][3];
  34. for (int j = 0; j < n; j++)
  35. {
  36. shops[j][0] = in.nextInt();
  37. shops[j][1] = in.nextInt();
  38. shops[j][2] = in.nextInt();
  39. }
  40. if (n == 1)
  41. {
  42. out.println(Math.min(shops[0][0], Math.min(shops[0][1], shops[0][2])));
  43. continue;
  44. }
  45. dp = new int[n][3];
  46. for (int j = 0; j < n; j++)
  47. Arrays.fill(dp[j], -1);
  48. int min = Math.min(shopping(0, 0, n), shopping(1, 0, n));
  49. min = Math.min(min, shopping(2, 0, n));
  50. out.println(min);
  51. }
  52. }
  53. static int shopping(int item, int i, int n)
  54. {
  55. if (dp[i][item] != -1)
  56. return dp[i][item];
  57. if (i == n - 1)
  58. {
  59. dp[i][item] = shops[i][item];
  60.  
  61. return dp[i][item];
  62. }
  63. else
  64. {
  65. dp[i][item] = shops[i][item]
  66. + Math.min(shopping((item + 1) % 3, i + 1, n),
  67. shopping((item + 2) % 3, i + 1, n));
  68. return dp[i][item];
  69. }
  70. }
  71.  
  72. static class InputReader
  73. {
  74. private InputStream stream;
  75. private byte[] buf = new byte[1024];
  76. private int curChar;
  77. private int numChars;
  78.  
  79. public InputReader(InputStream stream)
  80. {
  81. this.stream = stream;
  82. }
  83.  
  84. public int read()
  85. {
  86. if (numChars == -1)
  87. throw new InputMismatchException();
  88.  
  89. if (curChar >= numChars)
  90. {
  91. curChar = 0;
  92. try
  93. {
  94. numChars = stream.read(buf);
  95. }
  96. catch (IOException e)
  97. {
  98. throw new InputMismatchException();
  99. }
  100. if (numChars <= 0)
  101. return -1;
  102. }
  103.  
  104. return buf[curChar++];
  105. }
  106.  
  107. public int nextInt()
  108. {
  109. int c = read();
  110.  
  111. while (isSpaceChar(c))
  112. c = read();
  113.  
  114. int sgn = 1;
  115.  
  116. if (c == '-')
  117. {
  118. sgn = -1;
  119. c = read();
  120. }
  121.  
  122. int res = 0;
  123.  
  124. do
  125. {
  126. if (c < '0' || c > '9')
  127. throw new InputMismatchException();
  128.  
  129. res *= 10;
  130. res += c & 15;
  131.  
  132. c = read();
  133. } while (!isSpaceChar(c));
  134.  
  135. return res * sgn;
  136. }
  137. public int[] nextIntArray(int arraySize)
  138. {
  139. int array[] = new int[arraySize];
  140. for (int i = 0; i < arraySize; i++)
  141. array[i] = nextInt();
  142. return array;
  143. }
  144.  
  145. public long nextLong()
  146. {
  147. int c = read();
  148.  
  149. while (isSpaceChar(c))
  150. c = read();
  151.  
  152. int sign = 1;
  153.  
  154. if (c == '-')
  155. {
  156. sign = -1;
  157.  
  158. c = read();
  159. }
  160.  
  161. long result = 0;
  162.  
  163. do
  164. {
  165. if (c < '0' || c > '9')
  166. throw new InputMismatchException();
  167.  
  168. result *= 10;
  169. result += c & 15;
  170.  
  171. c = read();
  172. } while (!isSpaceChar(c));
  173.  
  174. return result * sign;
  175. }
  176. public long[] nextLongArray(int arraySize)
  177. {
  178. long array[] = new long[arraySize];
  179. for (int i = 0; i < arraySize; i++)
  180. array[i] = nextLong();
  181. return array;
  182. }
  183.  
  184. public float nextFloat() // problematic
  185. {
  186. float result, div;
  187. byte c;
  188.  
  189. result = 0;
  190. div = 1;
  191. c = (byte) read();
  192.  
  193. while (c <= ' ')
  194. c = (byte) read();
  195.  
  196. boolean isNegative = (c == '-');
  197.  
  198. if (isNegative)
  199. c = (byte) read();
  200.  
  201. do
  202. {
  203. result = result * 10 + c - '0';
  204. } while ((c = (byte) read()) >= '0' && c <= '9');
  205.  
  206. if (c == '.')
  207. while ((c = (byte) read()) >= '0' && c <= '9')
  208. result += (c - '0') / (div *= 10);
  209.  
  210. if (isNegative)
  211. return -result;
  212.  
  213. return result;
  214. }
  215.  
  216. public double nextDouble() // not completely accurate
  217. {
  218. double ret = 0, div = 1;
  219. byte c = (byte) read();
  220.  
  221. while (c <= ' ')
  222. c = (byte) read();
  223.  
  224. boolean neg = (c == '-');
  225.  
  226. if (neg)
  227. c = (byte) read();
  228.  
  229. do
  230. {
  231. ret = ret * 10 + c - '0';
  232. } while ((c = (byte) read()) >= '0' && c <= '9');
  233.  
  234. if (c == '.')
  235. while ((c = (byte) read()) >= '0' && c <= '9')
  236. ret += (c - '0') / (div *= 10);
  237.  
  238. if (neg)
  239. return -ret;
  240.  
  241. return ret;
  242. }
  243.  
  244. public String next()
  245. {
  246. int c = read();
  247.  
  248. while (isSpaceChar(c))
  249. c = read();
  250.  
  251. StringBuilder res = new StringBuilder();
  252.  
  253. do
  254. {
  255. res.appendCodePoint(c);
  256.  
  257. c = read();
  258. } while (!isSpaceChar(c));
  259.  
  260. return res.toString();
  261. }
  262.  
  263. public boolean isSpaceChar(int c)
  264. {
  265. return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  266. }
  267. public String nextLine()
  268. {
  269. int c = read();
  270. StringBuilder result = new StringBuilder();
  271. do
  272. {
  273. result.appendCodePoint(c);
  274. c = read();
  275. } while (!isNewLine(c));
  276. return result.toString();
  277. }
  278. public boolean isNewLine(int c)
  279. {
  280. return c == '\n';
  281. }
  282.  
  283. public void close()
  284. {
  285. try
  286. {
  287. stream.close();
  288. }
  289. catch (IOException e)
  290. {
  291. e.printStackTrace();
  292. }
  293. }
  294.  
  295. }
  296.  
  297. static class OutputWriter
  298. {
  299. private PrintWriter writer;
  300.  
  301. public OutputWriter(OutputStream stream)
  302. {
  303. writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
  304. stream)));
  305. }
  306.  
  307. public OutputWriter(Writer writer)
  308. {
  309. this.writer = new PrintWriter(writer);
  310. }
  311.  
  312. public void println(int x)
  313. {
  314. writer.println(x);
  315. }
  316.  
  317. public void print(int x)
  318. {
  319. writer.print(x);
  320. }
  321.  
  322. public void println(int array[], int size)
  323. {
  324. for (int i = 0; i < size; i++)
  325. println(array[i]);
  326. }
  327.  
  328. public void print(int array[], int size)
  329. {
  330. for (int i = 0; i < size; i++)
  331. print(array[i] + " ");
  332. }
  333.  
  334. public void println(long x)
  335. {
  336. writer.println(x);
  337. }
  338.  
  339. public void print(long x)
  340. {
  341. writer.print(x);
  342. }
  343.  
  344. public void println(long array[], int size)
  345. {
  346. for (int i = 0; i < size; i++)
  347. println(array[i]);
  348. }
  349.  
  350. public void print(long array[], int size)
  351. {
  352. for (int i = 0; i < size; i++)
  353. print(array[i]);
  354. }
  355.  
  356. public void println(float num)
  357. {
  358. writer.println(num);
  359. }
  360.  
  361. public void print(float num)
  362. {
  363. writer.print(num);
  364. }
  365.  
  366. public void println(double num)
  367. {
  368. writer.println(num);
  369. }
  370.  
  371. public void print(double num)
  372. {
  373. writer.print(num);
  374. }
  375.  
  376. public void println(String s)
  377. {
  378. writer.println(s);
  379. }
  380.  
  381. public void print(String s)
  382. {
  383. writer.print(s);
  384. }
  385.  
  386. public void println()
  387. {
  388. writer.println();
  389. }
  390.  
  391. public void printSpace()
  392. {
  393. writer.print(" ");
  394. }
  395.  
  396. public void flush()
  397. {
  398. writer.flush();
  399. }
  400.  
  401. public void close()
  402. {
  403. writer.close();
  404. }
  405.  
  406. }
  407.  
  408. }
Language: Java