#include<bits/stdc++.h>
using namespace std;
const int N=402,M=260981;
typedef long long ll;
const ll inf=1e18;
int out[N],in[N],s,t,n,m,x,y,z,w,h[N],cnt=1,gap[M],dep[N],ans[N],c[N];
struct hbs{int x,y,w;}f[N];
struct edge{int to,ne;ll val;}e[M];
int d(int x,int y){return (x-1)*(n+2)+y+1;}
void add(int x,int y,ll w){e[++cnt]={y,h[x],w},h[x]=cnt;}
void link(int x,int y,ll w){add(x,y,w),add(y,x,0);}
queue<int> q;
void bfs(int st){
memset(dep,0xff,sizeof(dep));
memset(gap,0,sizeof(gap));
q.push(st);
gap[dep[st]=0]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=h[x],y;i;i=e[i].ne){
y=e[i].to;
if(dep[y]<0){
gap[dep[y]=dep[x]+1]++;
q.push(y);
}
}
}
}
void bfs2(int st){
memset(dep,0xff,sizeof(dep));
q.push(st);
dep[st]=0;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=h[x],y;i;i=e[i].ne){
y=e[i].to;
if(e[i].val&&dep[y]<0){
dep[y]=dep[x]+1;
q.push(y);
}
}
}
}
ll dfs(int u,ll inflow){
if(u==t)return inflow;
ll outflow=0;
for(int &i=c[u];i;i=e[i].ne){
int v=e[i].to;
if(e[i].val&&dep[v]+1==dep[u]){
ll res=dfs(v,min(inflow-outflow,e[i].val));
e[i].val-=res,e[i^1].val+=res,outflow+=res;
if(inflow==outflow)return outflow;
}
}
if((--gap[dep[u]])==0)dep[s]=2*t;
dep[u]++,gap[dep[u]]++;
return outflow;
}
void ISAP(){
bfs(t);
while(dep[s]<2*t){
memcpy(c,h,sizeof(h));
dfs(s,1e18);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
f[i]={x,y,z};
out[x]+=z,in[y]+=z;
}
s=n*(n+2)+1,t=s+1;
for(int i=1;i<=n;++i){
for(int j=0;j<=n;++j)link(d(i,j),d(i,j+1),inf);
link(s,d(i,n+1),inf);
for(int j=0;j<=n;++j)link(s,d(i,j),out[i]);
link(d(i,0),t,inf);
for(int j=1;j<=n+1;++j)link(d(i,j),t,in[i]);
}
for(int i=1;i<=m;++i){
x=f[i].x,y=f[i].y;
for(int j=1;j<=n+1;++j)link(d(x,j),d(y,j-1),inf);
}
ISAP();
bfs2(s);
for(int i=1;i<=n;++i){
for(int j=n+1;j;--j){
ans[i]=j;
if(dep[d(i,j)]<0)break;
}
}
for(int i=1;i<=n;++i)printf("%d ",ans[i]);
return 0;
}
144. Binary Tree Preorder Traversal | 137. Single Number II |
130. Surrounded Regions | 129. Sum Root to Leaf Numbers |
120. Triangle | 102. Binary Tree Level Order Traversal |
96. Unique Binary Search Trees | 75. Sort Colors |
74. Search a 2D Matrix | 71. Simplify Path |
62. Unique Paths | 50. Pow(x, n) |
43. Multiply Strings | 34. Find First and Last Position of Element in Sorted Array |
33. Search in Rotated Sorted Array | 17. Letter Combinations of a Phone Number |
5. Longest Palindromic Substring | 3. Longest Substring Without Repeating Characters |
1312. Minimum Insertion Steps to Make a String Palindrome | 1092. Shortest Common Supersequence |
1044. Longest Duplicate Substring | 1032. Stream of Characters |
987. Vertical Order Traversal of a Binary Tree | 952. Largest Component Size by Common Factor |
212. Word Search II | 174. Dungeon Game |
127. Word Ladder | 123. Best Time to Buy and Sell Stock III |
85. Maximal Rectangle | 84. Largest Rectangle in Histogram |