// Author - Soumak Poddar ™
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define sll signed long long int
#define ull unsigned long long int
#define umax uintmax_t
 
#define um unordered_map
#define us unordered_set
#define mm multimap
#define pq priority_queue
#define pi pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define gi greater<int>
 
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define M 1000000007
 
template<typename T>
T gcd(T a,T b)
{
   if(a==0)
      return b;
   return gcd(b%a,a);
}
template<typename T>
T lcm(T a,T b)
{
   T g=gcd<T>(a,b);
   return (a*b)/g;
}
template<typename T>
bool isprime(T n)
{
   if(n<=1)
      return false;
   for(int i=2;i<sqrt(n);i++)
      if(n%i==0)
         return false;
   return true;
}
vector<bool> prime;
void seive(ll n=4000000)
{
   prime.resize(n+1);
   fill(prime.begin(),prime.end(),true);
   prime[0]=prime[1]=false;
   for(ll i=2;i*i<=n;i++)
   {
      if(prime[i]==true)
      {
         for(ll j=i*i;j<=n;j+=i)
            prime[j]=false;
      }
   }
}
// const ll s=1000000;
// vector<ll> pr;
// ll lp[s+1];
// void modified_sieve()
// {
//    for(int i=2;i<=s;i++)
//    {
//       if(lp[i]==0)
//       {
//          lp[i]=i;
//          pr.pb(i);
//       }
      
//       for(int j=0;j<(ll)pr.size() && pr[j]<=lp[i] && i*pr[j]<=s;++j)
//       {
//          lp[i*pr[j]]=pr[j];
//       }
//    }
// }
 
void solve();
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
 
   #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin);
      freopen("error.txt", "w", stderr);
      freopen("output.txt", "w", stdout);
   #endif
   
   ll t=1;
   // cin>>t;
   while(t--)
   {
      solve();
      // cout<<"\n";
   }
 
   cerr<<"Time Taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
   return 0;
}
 
um<int,vector<pi>> gr;
 
void dfs(int src,int dest,vi &path,vector<bool> &vis,vector<vi> &ans)
{
   if(src==dest)
   {
      ans.pb(path);
      return;
   }
 
   vis[src]=true;
   for(auto i:gr[src])
   {
      if(!vis[i.fir])
      {
         path.pb(i.sec);
         dfs(i.fir,dest,path,vis,ans);
         path.pop_back();
      }
   }
   vis[src]=false;
}
 
void solve()
{
   int n,m,k;
   cin>>n>>m>>k;
   for(int i=0;i<m;i++)
   {
      int u,v,w;
      cin>>u>>v>>w;
      gr[u].pb({v,w});
      gr[v].pb({u,w});
   }
 
   cout<<0<<" ";
   for(int i=2;i<=n;i++)
   {
      vector<bool> vis(n+1,false);
      vi v;
      vector<vi> ans;
      dfs(1,i,v,vis,ans);
      int soln=INT_MAX;
 
      for(auto i:ans)
      {
         if(i.size()<=k)
         {
            soln=0;
            break;
         }
 
         sort(i.begin(),i.end());
         int sz=i.size()-k;
         int sum=0;
 
         for(int ind=0;ind<sz;ind++)
            sum+=i[ind];
 
         soln=min(soln,sum);
      }
 
      cout<<soln<<" ";
   }
}