#include <bits/stdc++.h>
#define Hoshimachi signed
#define Suisei main
using namespace std;
#define int long long
#define pii pair<int,int>
#define tup tuple<int,int,int>
const int N=1e3+5;
int n,m,k;
vector<pii> adj[N];
int dp[(1<<10)+5][N];
void steiner(){
    memset(dp,0x3f,sizeof(dp));
    for(int i=0; i<k; i++){
        dp[(1<<i)][i]=0;
    }
    for(int mask=1; mask<(1<<k); mask++){
        for(int sub=mask; sub>0; sub=(sub-1)&mask){
            for(int i=0; i<n; i++){
                dp[mask][i]=min(dp[mask][i],dp[sub][i]+dp[mask^sub][i]);
            }
        }
        priority_queue<pii,vector<pii>,greater<pii>> q;
        for(int i=0; i<n; i++){
            q.push({dp[mask][i],i});
        }
        while(!q.empty()){
            auto [d,u]=q.top();
            q.pop();
            if(dp[mask][u]!=d) continue;
            for(auto [v,w]:adj[u]){
                int nd=d+w;
                if(dp[mask][v]>nd){
                    dp[mask][v]=nd;
                    q.push({nd,v});
                }
            }
        }
    }
    int fm=0;
    for(int i=0; i<k; i++){
        fm|=(1<<i);
    }
    for(int i=k; i<n; i++){
        cout<<dp[fm][i]<<'\n';
    }
}
bool ok[N];
tup e[N];
inline bool getbit(int n, int k){
    return (n>>k)&1;
}
struct Dsu{
    vector<int> sz,par;
    int sl;
    void init(int n){
        sl=n;
        sz.resize(n+1,1);
        par.resize(n+1,0);
        for(int i=0; i<n; i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return (x==par[x]?x:(par[x]=find(par[x])));
    }
    bool unite(int u,int v){
        u=find(u);
        v=find(v);
        if(u==v) return 0;
        sl--;
        if(sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];
        par[v]=u;
        return 1;
    }
};
Dsu dsu;
void krus(){
    vector<tup> all;
    for(int i=1; i<=m; i++){
        auto [u,v,w]=e[i];
        all.push_back({w,u,v});
    }
    sort(all.begin(),all.end());
    for(int i=0; i<k; i++) ok[i]=1;
    for(int st=k; st<n; st++){
        int kq=1e18;
        for(int mask=0; mask<(1<<n-k); mask++){
            if(!getbit(mask,st-k)) continue;
            for(int j=k; j<n; j++){
                if(getbit(mask,j-k)) ok[j]=1;
                else ok[j]=0;
            }
            dsu.init(n);
            dsu.sl=k+__builtin_popcountll(mask);
            vector<tup> edge;
            for(auto [w,u,v]:all){
                if(!ok[u] or !ok[v]) continue;
                edge.push_back({w,u,v});
            }
            int ans=0;
            for(auto [w,u,v]:edge){
                if(dsu.unite(u,v)) ans+=w;
            }
            if(dsu.sl==1) kq=min(kq,ans);
        }
        cout<<kq<<'\n';
    }
}
Hoshimachi Suisei(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);
    cin>>n>>m>>k;
    k--;
    for(int i=1; i<=m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        u--,v--;
        e[i]={u,v,w};
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    if(k<=10){
        steiner();
    }
    else{
        krus();
    }
}