#include <fstream>
#include <set>
#include <utility>
#include <queue>
#include <bitset>

using namespace std;

const int inf = 0x3f3f3f3f;

int N, M;
int cost[50010];
vector<pair<int, int> > G[50010];
bitset<50010> witness;
queue<int> Q;

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int i, A, B, C, node;
    vector<pair<int, int> >::iterator it;

    cin >> N >> M;
    fill_n(cost + 2, N, inf);

    for (i = 0; i < M; ++i)
    {
        cin >> A >> B >> C;
        G[A].push_back(make_pair(B, C));
    }

    Q.push(1);
    witness[1] = true;

    while(!Q.empty())
    {
        node = Q.front();
        witness[node] = false;

        for (it = G[node].begin(); it != G[node].end(); ++it)
        {
            if (cost[node] + it->second < cost[it->first])
            {
                cost[it->first] = cost[node] + it->second;
                if (witness[it->first] == false)
                {
                    Q.push(it->first);
                    witness[it->first] = true;
                }
            }
        }

        Q.pop();
    }

    for (i = 2; i <= N; ++i)
    {
        if (cost[i] == inf)
            cout << "0 ";
        else cout << cost[i] << ' ';
    }

    cout << '\n';
    cout.close();
    return 0;
}