#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5+10; int ans[MAXN],n,m; vector<pair<int,int> > g[MAXN]; int low[100], dfn[100], dfs_clock; bool isbridge[100][100]; int cnt_bridge; int father[100]; void tarjan(int u, int fa) { father[u]=fa; low[u]=dfn[u]=++dfs_clock; for (int i=0; i<g[u].size(); i++) { int v=g[u][i].first; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if (low[v]>dfn[u]){ isbridge[father[v]][v]=true; isbridge[v][father[v]]=true; ++cnt_bridge; } } else if(dfn[v]<dfn[u]&&v!=fa){ low[u]=min(low[u],dfn[v]); } } } void dfs(int u,int p,int dep,int val){ ans[dep]=min(ans[dep],val); for(pair<int,int> e:g[u]){ int v=e.first,w=e.second; if(v==p)continue; dfs(v,u,dep+1,val+w); } } bool inq[100]; queue<int> q; bool check(int s,int t){ memset(inq,0,sizeof(inq)); while(!q.empty())q.pop(); q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(pair<int,int> e:g[u]){ if(isbridge[u][e.first])continue; if(e.first==t)return true; if(!inq[e.first]){ q.push(e.first); inq[e.first]=true; } } } return false; } bool vis[100]; void dfs1(int u,int dep,int val){ ans[dep]=min(ans[dep],val); for(pair<int,int> e:g[u]){ int v=e.first,w=e.second; if(!vis[v]){ vis[v]=true; dfs1(v,dep+1,val+w); vis[v]=false; } } } bool bz[100][100]; void work1(){ tarjan(1,0); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)bz[i][j]=check(i,j); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(bz[i][j]){ g[i].push_back({j,0}); } vis[1]=true; dfs1(1,1,0); } int main(){ //freopen("trip.in","r",stdin); //freopen("trip.out","w",stdout); scanf("%d%d", &n, &m); for(int i=1;i<=m;i++){ int u,v,w; scanf("%d%d%d", &u, &v, &w); g[u].push_back({v,w}); g[v].push_back({u,w}); } for(int i=1;i<=n;i++)ans[i]=INT_MAX; if(n>100)dfs(1,0,1,0); else work1(); for(int i=2;i<=n;i++) if(ans[i]==INT_MAX)printf("INF\n"); else printf("%d\n", ans[i]); return 0; } /* 8 9 1 2 5 1 3 5 3 4 4 3 5 2 5 6 1 6 7 4 6 8 5 3 8 1 4 8 3 */