#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define maxn 50001
using namespace std;

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

vector < pair <int,int> >Graf[maxn];
int best[maxn];
struct comp
{
    inline bool operator () (const int &A,const int &B) const
    {
        return best[A] > best[B];
    }
};

priority_queue < int,vector<int>,comp > Q;
void Dijkstra()
{
    memset(best,0x3f,sizeof(best));
    best[1]=0;
    Q.push(1);
    vector < pair<int,int> > :: iterator it;
    while(!Q.empty())
        {
            int now;
            now=Q.top();
            Q.pop();
            for(it=Graf[now].begin();it!=Graf[now].end();it++)
                if(best[now]+it->second < best[it->first] )
                    {
                        best[it->first]=best[now]+it->second;
                        Q.push(it->first);
                    }
        }

}

int main()
{
    int n,m;
    int a,b,c;
    in>>n>>m;
    while(m--)
    {
        in>>a>>b>>c;
        Graf[a].push_back(make_pair(b,c));
    }
    Dijkstra();

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