#include <fstream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
struct varf{
    int x, cost;
};
int dist[50005];
int ver[50005];
struct comp{
    bool operator() (int a, int b)
    {
        return dist[a] > dist[b];
    }
};
vector<varf>g[50005];
int n,m,c1,c2,val;

void dijkstra(int inceput)
{
    priority_queue<int, vector<int>, comp>q;
    dist[inceput]=0;
    ver[inceput]=1;
    q.push(inceput);
    while (!q.empty())
    {
        int nod=q.top();
        ver[nod]=0;
        for (int i=0;i<g[nod].size();i++)
        {
            int vecin=g[nod][i].x;
            int costul=g[nod][i].cost;
            if (dist[vecin]>dist[nod]+costul)
            {
                dist[vecin]=dist[nod]+costul;
                if (ver[vecin]==0)
                {
                    ver[vecin]=1;
                    q.push(vecin);
                }
            }
        }
        q.pop();
    }
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>c1>>c2>>val;
        g[c1].push_back({c2,val});
    }
    for (int i=1;i<=n;i++)
        dist[i]=INF;
    dijkstra(1);
    for (int i=2;i<=n;i++)
        cout<<dist[i]<<' ';
    return 0;
}