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

void dijkstra(int inceput)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> >q;
    for (int i=1;i<=n;i++)
        dist[i]=INF;
    dist[inceput]=0;
    q.push({0,inceput});
    while (!q.empty())
    {
        int minim=q.top().first;
        int vfmin=q.top().second;
        q.pop();
        if (ver[vfmin]==1)
            continue;
        ver[vfmin]=1;
        for (int i=0;i<g[vfmin].size();i++)
        {
            int vecin=g[vfmin][i].x;
            int costul=g[vfmin][i].cost;
            if (dist[vecin]>dist[vfmin]+costul)
            {
               dist[vecin]=dist[vfmin]+costul;
               q.push({dist[vecin],vecin});
            }
        }
    }
}

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