#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

const int MAX = 50005;
const int INF = 1e9;

int n, m, a, b, c, dist[N], viz[N];

struct graf
{
    int nod, cost;
};

vector < graf > g[MAX];

struct cmp
{
    bool operator()(graf a, graf b)
    {
        return a.cost > b.cost;
    }
};

priority_queue < graf, vector < graf >, cmp > q;

void dijkstra(int s)
{
    for (int i = 1; i <= n; ++i)
        dist[i] = INF;
    dist[s] = 0;
    q.push({s, 0});
    viz[s] = 1;
    while(!q.empty())
    {
        int u = q.top().nod;
        viz[u] = 0;
        q.pop();
        for(int j = 0; j < g[u].size(); ++j)
        {
            int v = g[u][j].nod;
            int duv = g[u][j].cost;
            if(dist[u] + duv < dist[v])
            {
                dist[v] = dist[u] + duv;
                if(!viz[v])
                {
                    q.push({v, dist[v]});
                    viz[v] = 1;
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while(m--)
    {
        cin >> a >> b >> c;
        g[a].push_back({b, c});

    }
    dijkstra(1);
    for(int i = 2; i <= n; ++i)
    {
        if(dist[i] == INF)
            cout << "0 ";
        else
            cout << dist[i] << ' ';
    }
    return 0;
}