//Vasilut
//Dijkstra cu Heapuri (implementare cu ajutorul unui set din STL)

#include<fstream>
#include<vector>
#include<set>
#include<utility>


#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define NN 50001
#define f first
#define s second


using namespace std;
ofstream out("dijkstra.out");

int n,m;
vector<pair<int,int > > G[NN];
vector<int>dist;
vector<bool>uz(n+1,0);
set<pair<int,int > >S;
typedef set<pair<int ,int > >::iterator IT;

void read();
void Dijkstra();
void write();

int main()
{
    read();
    Dijkstra();
    write();
    return 0;
}

void read()
{
    ifstream in("dijkstra.in");
    in>>n>>m;
    for(int x,y,c; m ;--m)
    {
        in>>x>>y>>c;
        G[x].pb(mp(y,c));
    }
}

void write()
{
        for(int i=2;i<=n;i++)
            if(dist[i] == INF )
                out<<0<<" ";
                else
                out<<dist[i]<<" ";
}


void Dijkstra()
{
    dist.resize(n+1,INF);
    dist[1]=0;
    S.insert(mp(0,1));
    while(!S.empty())
    {
        IT I=S.begin();
        S.erase(I);
        int nod=I->s;
        int val=I->f;
        for(int i=0; (int ) i<G[nod].size(); ++i)
        {
            int son=G[nod][i].f;
            int muchie=G[nod][i].s;
            if( dist[son] > val + muchie )
                {
                    dist[son]= val + muchie;
                    S.insert(mp(dist[son],son));
                }
        }
    }
}