#include<fstream>
#include<vector>
#include<queue>
#define MAXN 50001
#define INF 1<<30
#define cost first
#define poz second
using namespace std;

void read();
void dijkstra(int);
void write();

vector< pair<int,int> > graph[MAXN];
vector<int> dist(MAXN,INF);
int n,m,from,to,costul,i;
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > myHeap;

int main()
{
    read();
    dijkstra(1);
    write();
    return 0;
}

void read()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>from>>to>>costul;
        graph[from].push_back(make_pair(costul,to));
    }
    in.close();
}

void dijkstra(int StartNode)
{
    dist[StartNode]=0;
    pair<int,int> CurrentNode;
    vector< pair<int,int> >::iterator vecin;
    vector< pair<int,int> >::iterator end;
    myHeap.push(make_pair(0,StartNode));
    while(!myHeap.empty())
    {
        CurrentNode=myHeap.top();
        myHeap.pop();
        end=graph[CurrentNode.poz].end();
        for(vecin=graph[CurrentNode.poz].begin();vecin!=end;vecin++)
            if(dist[vecin->poz]>dist[CurrentNode.poz]+vecin->cost)
            {
                dist[vecin->poz]=dist[CurrentNode.poz]+vecin->cost;
                myHeap.push(make_pair(dist[vecin->poz],vecin->poz));
            }
    }

}

void write()
{
    ofstream out("dijkstra.out");
    for(i=2;i<=n;i++)
        out<<(dist[i]==INF ? 0:dist[i])<<" ";
    out.close();
}