#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int INF=0x3f3f3f3f;

struct muchie
{
    int nod,cost;
};

struct heap
{
    int nod,cost,anterior;
    inline bool operator <(const heap &other) const
    {
        return cost>other.cost;
    }
};

priority_queue <heap> H;
vector <muchie> G[50005];

int dist[50005];
int frecventa[50005];

void dijkstra(int nod_plecare)
{
    heap nod_curent;
    nod_curent.nod=nod_plecare;
    nod_curent.cost=0;
    nod_curent.anterior=-1;
    dist[nod_curent.nod]=0;
    H.push(nod_curent);
    while(!H.empty())
    {
        nod_curent=H.top();
        H.pop();
        if(frecventa[nod_curent.nod]>=1)
        {
            continue;
        }
        frecventa[nod_curent.nod]++;
        for(int i=0; i<G[nod_curent.nod].size(); i++)
        {
            heap vecin;
            vecin.nod=G[nod_curent.nod][i].nod;
            vecin.cost=G[nod_curent.nod][i].cost+dist[nod_curent.nod];
            vecin.anterior=nod_curent.nod;
            if(vecin.cost<dist[vecin.nod])
            {
                dist[vecin.nod]=vecin.cost;
                H.push(vecin);
            }
        }
    }
}

int main()
{
    int n,m;
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        muchie curent;
        curent.nod=b;
        curent.cost=c;
        G[a].push_back(curent);
    }
    for(int i=1;i<=n;i++)
    {
        dist[i]=INF;
    }
    dijkstra(1);
    for(int i=2;i<=n;i++)
    {
        out<<dist[i]<<' ';
    }
    out<<'\n';
}