#define inf 0x3f3f3f3f
#define NMAX 50005
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int Dmin[NMAX], viz[NMAX];

vector<pair<int, int>> graph[NMAX];
priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;


void read()
{
    int x, y, c;
    scanf("%d %d", &n, &m);

    for(int i=0; i<m; ++i){
        scanf("%d %d %d", &x, &y, &c);
        graph[x].push_back({c, y});
    }
}

void solve()
{
    Q.push({0, 1});
    viz[1] = 1;

    while(!Q.empty())
    {
        pair<int, int> t = Q.top();
        Q.pop();
        viz[t.second] = 0;

        for(auto &v:graph[t.second])
            if(Dmin[v.second] > Dmin[t.second] + v.first)
            {
                Dmin[v.second] = Dmin[t.second] + v.first;
                if(viz[v.second] == 0)
                {
                    Q.push({Dmin[v.second], v.second});
                    viz[v.second] = 1;
                }
            }

    }
}

void init()
{
    for(int i=2; i<=n; ++i)
        Dmin[i] = inf;
}


void write()
{
    for(int i=2; i<=n; ++i)
        printf("%d ", Dmin[i]);
}



int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    read();
    init();
    solve();
    write();
    return 0;
}