#include <bits/stdc++.h>
using namespace std;

#define INF 20001
#define NRMAX 50001

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

priority_queue<pair<int,int>>Q;
vector <pair<int,int>>A[NRMAX];
int viz[NRMAX], dist[NRMAX];

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a, b, c;
        fin>>a>>b>>c;
        A[a].push_back({b,c});
    }

    for(int i=1; i<=n; i++)
    {
        dist[i]=INF;
        viz[i]=0;
    }

    dist[1]=0;
    Q.push({0,1});

    while(!Q.empty())
    {
        int a=Q.top().second;
        Q.pop();
        if(viz[a])
            continue;
        viz[a]=1;
        for(auto u:A[a])
        {
            int b=u.first;
            int c=u.second;
            dist[b]=min(dist[b], dist[a]+c);
            Q.push({-c, b});
        }
    }

    for(int i=2; i<=n; i++)
        fout<<dist[i]<<" ";
    return 0;
}