//106min
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace  std;
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rep(n) for (int i = 0; i < n; ++i)

const int md = 1e9 + 7; //998244353 ;
void addto(int &x, int y) { x = x + y; if (x >= md) x -= md; }
int add(int x, int y) { int z = x + y; return z >= md? z -= md : z;}
void updmin(auto&x, auto y ) { if (y < x) x = y;}
void updmax(auto&x, auto y ) { if (y > x) x = y;}
long long pw(auto x, auto y) {	
	long long s = 1;
	while(y) {
		if (y & 1) s = s * x % md;
		x= 1LL * x * x % md; y /= 2;
	}
	return s;
}


const int maxn = 1e6 + 10;

int T, n, m;
int v[maxn];
	
vector<tuple<int, int, int> > a(1, {0,0,0});
vector<ll> ans;
void solve_dp(vector<tuple<ll, ll>> &p, vector<vector<ll>> &dp) {
	debug("solve_dp", p.size());
	sort(p.begin(), p.end());
	int n = p.size() - 1;

	vector<ll> s(p.size()), a(p.size());
	for (int i = 1; i <= n; ++i) {
		a[i] = get<1>(p[i]);
		s[i] = a[i] * get<0>(p[i]);
		a[i] += a[i - 1];
		s[i] += s[i - 1];
	}
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = s[i];
	}
	debug("solve_dp_init");
	//for (int i = 1; i <= n; i++) {
		//for (int j = 1; j <= i; ++j) {
			//int t = i; 
			//for (int k = i - 1; k >= 0; --k) {
				//while (t > k + 1 ){
					 //ll cost1 = s[i] -s[k] - 2*(s[t] - s[k]) - get<0>(p[t]) * (a[i] - a[k] - 2*(a[t] - a[k]));
					 //ll cost2 = s[i] -s[k] - 2*(s[t - 1] - s[k]) - get<0>(p[t - 1]) * (a[i] - a[k] - 2*(a[t - 1] - a[k]));
					 //if (cost1 >= cost2) t--; else break;					 
				//}
		    //ll cost = s[i] -s[k] - 2*(s[t] - s[k]) - get<0>(p[t]) * (a[i] - a[k] - 2*(a[t] - a[k]));
				//dp[i][j] = min(dp[i][j], dp[k][j-1] + cost);
			//}
		//}
	//}
	vector<vector<ll>> cost(dp.size(), vector<ll>(dp[0].size(), 0));
	for (int i = 1; i <= n; ++i)  {
		int t = i;
		for (int k = i - 1; k >= 0; --k) {
				int t = i; 
				while (t > k + 1 ){
					 ll cost1 = s[i] -s[k] - 2*(s[t] - s[k]) - get<0>(p[t]) * (a[i] - a[k] - 2*(a[t] - a[k]));
					 ll cost2 = s[i] -s[k] - 2*(s[t - 1] - s[k]) - get<0>(p[t - 1]) * (a[i] - a[k] - 2*(a[t - 1] - a[k]));
					 if (cost1 >= cost2) t--; else break;					 
				}
				cost[k + 1][i] = s[i] -s[k] - 2*(s[t] - s[k]) - get<0>(p[t]) * (a[i] - a[k] - 2*(a[t] - a[k]));
		} 
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= n; ++i) {
			for (int k = i - 1; k >= 0; --k) {
				dp[i][j] = min(dp[i][j], dp[k][j-1] + cost[k+1][i]);
			}
		}
	}
}
vector<vector<ll>> merge(vector<vector<ll>> dp1, 	vector<vector<ll>> dp2) {
	debug("merge");
	int n1 = dp1.size() - 1;
	int n2 = dp2.size() - 1;
	int m1 = dp1[0].size() - 1;
	int m2 = dp2[0].size() - 1;
	vector<vector<ll>> dp(n1 + n2 + 1, vector<ll> (m1 + m2 + 1, 1e18));	
	int n = n1 + n2, m = m1 + m2;
	for (int i = 0 ; i <= m; ++i) 
		for (int j = 0; j <= i; ++j) {
			if (j > m1 || i - j > m2) continue;
			dp[n][i] = min(dp[n][i], dp1[n1][j] + dp2[n2][i - j]);
		} 
	return dp;	
}
void solve() {
	vector<tuple<ll, ll>> p1(1), p2(1), q1(1), q2(1);

	for (int i = 1; i <= n; ++i) {
		int x, y, z;
		tie(x, y, z) = a[i];
		if (v[i] == 0 && x >= 0) p1.emplace_back(x, z);
		if (v[i] == 0 && x < 0) p2.emplace_back(-x, z);
		if (v[i] == 1 && y >= 0) q1.emplace_back(y, z);
		if (v[i] == 1 && y < 0) q2.emplace_back(-y, z);

	}
	debug(n, p1. size(), p2.size(), q1.size(), q2.size());
	vector<vector<ll>> dp_p1(p1.size(), vector<ll>(p1.size(), 1e18)), dp_q1(q1.size(), vector<ll>(q1.size(), 1e18)); 
	vector<vector<ll>> dp_p2(p2.size(), vector<ll>(p2.size(), 1e18)), dp_q2(q2.size(), vector<ll>(q2.size(), 1e18)); 
	
	solve_dp(p1, dp_p1);   
	solve_dp(p2, dp_p2);
	dp_p1 = merge(dp_p1, dp_p2);
	solve_dp(q1, dp_q1);
	solve_dp(q2, dp_q2);
	dp_q1 = merge(dp_q1, dp_q2);
	dp_p1 = merge(dp_p1, dp_q1);
	debug(dp_p1.size(), dp_p1[0].size());
	debug(dp_p1[n]);
	for (int i =  0; i <= n; ++i) {
		ans[i] = min(ans[i], dp_p1[n][i]);
	}
}
void dfs(int dep) {
	if (dep > n) {
		solve();
		return;
	}
	v[dep] = 0;
	dfs(dep + 1);
	v[dep] = 1;
	dfs(dep + 1);
	
}
void task() {
	cin >> n;
	a.clear(); a.emplace_back(0, 0, 0);
	ans = vector<ll>(n + 1, 1e18);
	for (int i = 1; i <= n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		a.emplace_back(x, y , z);
	}
	dfs(1);
	for (int i = 0; i <= n; ++i) {
		cout << ans[i] << endl;
	}
	// you should actually read the stuff at the bottom
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout<<fixed<<setprecision(20);
  T = 1;
  for (int ti = 1; ti <= T; ++ti) {
    task();
  }
  return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* write down
*/


Measured memory_bytes: 3700