Devu, his sister and Rangoli

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
As you know already, it is Devu's birthday today. He wants to make a Rangoli to decorate his house. He created n points having integer coordinates on the front door of his house. He also made sure no three points are collinear in it because collinear points break beauty of it. For each point, there is parameter beauty which is a positive integer.
Now, when Devu's little sister saw the points drawn, she thought of creating patterns by drawing a convex polygon by choosing some of the n point as vertices of it. Also, as she is very naughty, instead of creating most beautiful pattern, she wants to create least beautiful pattern. Beauty of a polygon is sum of beauties of all the points lying inside or on the boundary of it.
You have to help Devu's sister in finding out the least beauty of convex polygon of k vertices. If it is impossible to find such a convex polygon, print 1. Otherwise print the minimum weight of the convex polygon you can have. Please solve the problem for all k's from 3 to n.
Input
 There is a single test case.
 First line contains a single integer n as defined in the problem.
 Then in the next n lines, each line contains three space separated integers x, y, b denoting that there is a point with coordinates (x, y) with beauty equal to b.
Output
Print n  2 space separated integers corresponding to the answer for k = 3 to n as asked in the problem.
Constraints
 3 ≤ n ≤ 50
  10^{5} ≤ x, y ≤ 10^{5}
 1 ≤ b ≤ 10^{5}
 No three or more points are collinear.
 All the points in the input are distinct.
Example
Input: 3 0 0 1 1 0 2 0 1 3 Output: 6
Input: 4 0 0 1 1 0 2 0 1 3 1 1 2 Output: 5 8
Explanation
Example case 1. The triangle given in the input has beauty equal to 6.
Example case 2. One of the triangles has a beauty of 5 whereas there is only one rectangle which has beauty equal to 8.
Author:  admin2 
Editorial  http://discuss.codechef.com/problems/MINPOLY 
Tags  admin2, cook58, geometry, hard 
Date Added:  21052015 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 