#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <cctype>

#define NMAX 1005
#define KMAX 1005
using namespace std;

int k;
vector <pair <int, int> > graf[NMAX];
vector <int> vals[NMAX];
bool done[NMAX];

priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > _queue;

int ind[NMAX];
int cost[NMAX];

void dfs (int node, int father) {
    if (done[node])
        return ;
    done[node] = true;

    for (vector <pair <int, int> > :: iterator it = graf[node].begin(); it != graf[node].end(); it++)
        if (it -> first != father)
            dfs(it -> first, node);

    for (vector <pair <int, int> > :: iterator it = graf[node].begin(); it != graf[node].end(); it++)
        if (it -> first != father)
            if (!vals[it -> first].empty()) {
                ind[it -> first] = 0;
                cost[it -> first] = it -> second;

                _queue.push(make_pair(it -> second + vals[it -> first][0], it -> first));
            }

    int y;
    for (int i = 0; i < k && !_queue.empty(); i++) {
        y = _queue.top().second;
        vals[node].push_back(_queue.top().first);
        _queue.pop();

        ind[y] ++;
        if (ind[y] < vals[y].size())
            _queue.push(make_pair(vals[y][ind[y]] + cost[y], y));
    }

    while (!_queue.empty())
        _queue.pop();
}

char sir[3602705];
int poz, lung;

ifstream cin("pitici.in");
inline void get () {
    cin.get(sir + 1, 3602705, '#');
    lung = strlen(sir + 1);
    poz = 1;
}

inline int extr () {
    while (poz <= lung && !isdigit(sir[poz]))
        poz ++;

    int ans = 0;
    while (poz <= lung && isdigit(sir[poz])) {
        ans *= 10;
        ans += (sir[poz] - '0');

        poz ++;
    }

    return ans;
}

int main()
{
    ofstream cout("pitici.out");

    int n, m;
    cin >> n >> m >> k;

    get();

    int a, b, c;
    while (m--) {
        //cin >> a >> b >> c;
        a = extr();
        b = extr();
        c = extr();

        graf[a].push_back(make_pair(b, c));
    }

    vals[n].push_back(0);
    done[n] = true;

    dfs(1, 0);

    cout << vals[1][0];
    for (int i = 1; i < k; i++)
        cout << ' ' << vals[1][i];
    cout << '\n';

    cin.close();
    cout.close();
    return 0;
}