#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
#include <bitset>

#define INF 0x3f3f3f3f

using namespace std;

typedef pair < int , int > pii;

vector < pii > v[50002];
priority_queue < pii , vector < pii > , greater < pii > > q;
bitset < 50002 > mark;

int d[50002];

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, c; f >> a >> b >> c;
        v[a].push_back({b, c});
    }

    memset(d, INF, sizeof(d));
    d[1] = 0;
    for(int i = 1; i <= n; i++)
        q.push({d[i], i});

    while(!q.empty())
    {
        int x = q.top().second;
        q.pop();
        mark[x] = 0;

        for(auto nb: v[x])
        {
            int y = nb.first, c = nb.second;
            if(d[x] + c < d[y])
            {
                d[y] = d[x] + c;
                if(!mark[y])
                {
                    q.push({d[y], y});
                    mark[y] = 1;
                }
            }
        }
    }

    for(int i = 2; i <= n; i++)
    {
        if(d[i] == INF) d[i] = 0;
        g << d[i] << ' ';
    }
    g << '\n';
    f.close();
    g.close();
    return 0;
}