#include <bits/stdc++.h>
#define fs first
#define sc second

using namespace std;

ifstream f("dijkstra.in");
ofstream gg("dijkstra.out");

int n,m;
int sel[1005],t[1005],d[10005];

typedef pair <int,int> pi;

vector <pi> g[1005];
priority_queue <pi, vector <pi>, greater <pi> > q;

const int inf=INT_MAX;

void init()
{
    for (int i=1; i<=n; i++ )
    {

        sel[i]=false;
        d[i]=inf;
        t[i]=0;
    }
}

void dijkstra (int p)
{
    init();
    sel[p]=true;
    d[p]=0;

    for (auto i:g[p] )
    {
        q.push(i);
        d[i.sc]=i.fs;
    }

    while ( !q.empty() )
    {
        while ( !q.empty() && sel[q.top().sc] )
            q.pop();

        if ( q.empty() )
            break;

        int k=q.top().sc;
        int c=q.top().fs;

        q.pop();

        sel[k]=true;
        d[k]=c;

        for (auto i:g[k] )
        {
            if ( !sel[i.sc] && c+i.fs<d[i.sc] )
            {
                q.push({c+i.fs,i.sc});
                t[i.sc]=k;
            }
        }
    }
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; i++ )
    {
        int x,y,c;
        f >> x >> y >> c;
        g[x].push_back({c,y});
    }
    dijkstra(1);

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